Understanding Binary and Non-Binary Trees: Structure, Implementation, and Complexity Analysis | CodeSignal Learn

Understanding Binary and Non-Binary Trees: Structure, Implementation, and Complexity Analysis | CodeSignal Learn

Introduction and Overview

Welcome, Explorer! Today, we will delve deeper into the fascinating world of tree-based data structures. Building upon our comprehensive understanding of these structures, we're ready to enhance our knowledge further. Today's lesson focuses on Binary and Non-Binary Trees : their basic structure, implementation, complexity analyses, and the core operations performed on them. As a reminder, tree data structures possess an impressive versatility that allows them to tackle many complex problems. For instance, managing hierarchies of employees in a large organization or efficiently storing words in a spell-checking system — these real-world scenarios naturally form tree-like structures!

Conceptual Overview: Binary and Non-Binary Trees

E = V - 1

Implementation of Binary and Non-Binary Trees

Now that we've refreshed our understanding of what binary and non-binary trees are let's illustrate how to implement them using Python. In Python, tree structures can be constructed using class-based representations. A class is essentially a blueprint for creating objects. Objects have member variables and exhibit behaviors associated with them. Consider the binary tree. Below is the Node class, representing a single node in a binary tree. Each Node object can hold a value and has two pointers, left and right, initially set to None . Python class Node: def __init__(self, value): self.value = value self.left = None self.right = None For a non-binary tree, we can use a list to hold the links to the child nodes since their number isn't fixed. Python class Node: def __init__(self, value): self.value = value self.children = [] We can create individual nodes, link them as children or parents, and construct our desired trees.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Example: Binary Tree

In order to gain a practical understanding of the concepts presented so far, let's take a look at some examples of binary and non-binary trees along with their traversals. For our binary tree, let's use a simple structure with three levels of vertices. Here is how we define it in Python: Python # Creating nodes for the tree. root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6)

Example: Non-Binary Tree

As for the non-binary tree, we demonstrate a simple tree with three levels. Here is how we define it in Python: Python # Creating nodes for the tree. root = Node(1) root.children = [Node(2), Node(3), Node(4)] root.children[0].children = [Node(5), Node(6)] root.children[2].children = [Node(7)]

Binary Tree Traversal

Trees are dynamic data structures permitting several operations, such as insertion (adding a new node), deletion (removing an existing node), and traversal (accessing or visiting all nodes in a specific order). Traversal of the binary tree is a process of visiting all nodes of a tree and possibly printing their values. Since all nodes are connected via edges (links), we always start from the root (head) node. We cannot randomly access a node in a tree. There are three ways to traverse a tree: In-order Traversal : In this method, the left subtree is visited first, then the root, and later the right subtree. We should always remember that every node may represent a subtree itself. Pre-order Traversal : In this method, the root node is visited first, then the left subtree, and finally the right subtree. Post-order Traversal : In this method, the root node is visited last, hence the name. We first traverse the left subtree, then the right subtree, and finally, the root node. Here is how the in-order traversal implementation may look like: Python def in_order_traversal(node): if node is None: return in_order_traversal(node.left) print(str(node.value) + ' -> ', end='') in_order_traversal(node.right) in_order_traversal(root) # Output: 4 -> 2 -> 5 -> 1 -> 3 -> 6 -> Considering the binary tree from the example above, the in-order traversal will be 4 -> 2 -> 5 -> 1 -> 3 -> 6 .

Tree Operations: Insertion and Deletion

Usually, information is inserted into a tree as a node. In a binary tree, a new node is inserted as the left or the right child of an existing node. An algorithm for inserting a node can be established by identifying an appropriate location for the new node. Deleting a node from a tree structure requires identifying the node, studying its properties, and subsequently transforming the tree structure. Here's how our tree definitions look with these operations implemented: Python class TreeNode: def __init__(self, value): self.value = value self.children = [] def add_child(self, child_node): self.children.append(child_node) def remove_child(self, child_node): self.children = [child for child in self.children if child is not child_node] In these examples, the add_child and remove_child methods enable us to add a node and remove a node in the tree, respectively.