Binary Tree Data Structure

⌚ What is binary tree?

A binary tree is defined as a tree with no more than two offspring. Because each binary tree element can only have two offspring, we call them the left and right child. It has following parts
Data
Left child Pointer
Right child Pointer

⌚ Explain the different types of Binary Tree

• Full Binary Tree: It's a specific type of binary tree that contains either zero or two children. It means that every binary tree node should have two children, or that the parent node should be the leaf node or the external node itself.
• Complete Binary Tree: A complete binary tree is another sort of binary tree in which all of the tree levels, except the lowest, are completely filled with nodes. Furthermore, the last or lowest level of the binary tree should have every node on the left side.
• Perfect Binary Tree: If all internal nodes have exactly two children and every external or leaf node is at the same level or depth within the tree, it is said to be 'perfect.' 2h – 1 node in a perfect binary tree of height 'h'
• Balanced Binary Tree: A tree is considered to be balanced if its height is O(logN), where N is the number of nodes. In a balanced binary tree, the height of each node's left and right subtrees should differ by no more than one. A data structure like an AVL Tree or a Red-Black Tree can be used to create a balanced binary search tree.
• Degenerate Binary Tree: If every internal node has only one child, the binary tree is considered to be degenerate binary tree or pathological binary tree. In terms of performance, such trees are similar to linked lists.

⌚ Explain the benefits of a Binary Tree

A binary tree's search method is faster than that of other trees.
Only two traversals are required to sort the elements. It is simple to select the maximum and minimum elements.
Binary trees are also used in graph traversal.
Various postfix and prefix expressions can be converted using binary trees.

⌚ Explain some of the properties of Binary Tree

The maximum number of nodes in a binary tree at level 'n' is 2ⁿ.
In a binary tree of height 'h,' the maximum number of nodes is 2^h – 1.
The number of leaf nodes in a binary tree with 0 or 2 children is always one more than the number of nodes with two children.
The minimum feasible height or number of layers in a Binary Tree with N nodes is Log2(N+1).
There are at least | Log2L |+ 1 levels in a Binary Tree with L leaves.

⌚ What are the different types of tree traversals?

Traversal is a method of visiting every node in a tree and publishing their values. Because all nodes are connected by edges, we always start with the root (head) node (links). That is, a node in a tree cannot be accessed at random. We can navigate a tree in three different ways.
In-order Traversal
Pre-order Traversal
Post-order Traversal

⌚ Explain each of the tree traversal?

Inorder Traversal: The Left Root Right policy is followed by an inorder traversal strategy. Left Root Right denotes that the root node's left subtree is explored first, followed by the root node, and finally the right subtree of the root node. The name inorder suggests that the root node is situated between the left and right subtrees.

Inorder Traversal:
1. To explore the left subtree, call Inorder (left-subtree)
2. Go to the source.
3. Call Inorder to traverse the correct subtree (right-subtree)

Preorder Traversal:
In preorder traversal, the root node is always traversed first, whereas in postorder traversal, it is traversed last. Preorder traversal is used to find a tree's prefix expression.
Algorithm Preorder(tree)
1. Go to the source.
2. Call Preorder from the left subtree (left-subtree)
3. Navigate to the appropriate subtree, i.e., call Preorder (right-subtree)

Postorder Traversal: One of the traversing techniques used to visit the node in the tree is postorder traversal. The LRN concept supports it (Left-right-node). Postorder traversal is used to find a tree's postfix expression.
Algorithm Postorder(tree)
1. To explore the left subtree, use Postorder (left-subtree)
2. Call Postorder from the appropriate subtree (right-subtree)
3. Go to the source.

⌚Implement Inorder traversal without recursion?

The obvious technique to traverse a tree without recursion is to use Stack. The algorithm for traversing a binary tree using stack is shown below. See this for the algorithm's step-by-step execution.

1. Make an empty stack called St.
2. Start with current node as root
3. push the current node to St and set current = current->left until current is NULL.
4. If current is NULL and the stack isn't empty, a) Remove the top item from the stack.
b) Set current = popped item->right to print the popped item.
c) Continue to step 3
5. We're done if current is NULL and stack is empty.

from collections import deque
 
 
# Data structure to store a binary tree node
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
 
# Iterative function to find inorder traversal of the binary tree
def inorderIterative(root):
 
    # create an empty stack
    stack = deque()
 
    # start from the root node (set current node to the root node)
    curr = root
 
    # if the current node is None and the stack is also empty, we are done
    while stack or curr:
 
        # if the curr node exists, push it into the stack
        # and then traverse to its left child
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            # or, if the curr node is Null, pop out the element from the stack,
            # print it, and then set the curr node to its right spring
            curr = stack.pop()
            print(curr.data, end=' ')
 
            curr = curr.right
 
 
if __name__ == '__main__':
 
 
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.left = Node(7)
    root.right.left.right = Node(8)
 
    inorderIterative(root)

The above solutions have an O(n) time complexity, where n is the total number of nodes in the binary tree. The program's space complexity is O(n), because the space required is proportional to the tree's height.

⌚ Implement Inorder traversal without recursion and without using stack?

Because a tree is not a linear data structure and nodes might have multiple child nodes, there may be numerous nodes to visit after a node has been visited. Nodes that need to be visited later must be saved in some way for future visits.

This can be accomplished by either saving the nodes in a stack for future visits or by utilising recursion, in which the nodes are implicitly saved in a stack for future visits. It's about using Morris Traversal to achieve inorder tree traversal without requiring recursion or stack.

Morris Traversal is based on the Threaded Binary Tree concept. We build links to Inorder successors and display the data using these links in this traversal, then undo the changes to restore the original tree.

Steps involve in Morris Traversal
1. Create in-order successor linkages
2. Using the formed links, print the information (the tree is altered during the traversal)
3. Revert the changes and restore the original tree after the traversal is complete.

Algorithm:

1. Set the root to be the current node curr.
2. Check if curr has a left child when it is not NULL.
3. If curr has no left child, print curr and update it to point to the node to curr's right.
4. Otherwise, make curr the right child of curr's left subtree's rightmost node.
5. Curr should be updated to this left node.

class Node: 
	def __init__(self, data): 
		self.data = data 
		self.left_node = None
		self.right_node = None

def Morris(root): 
	# Set current to root of binary tree 
	curr = root 
	
	while(curr is not None): 
		
		if curr.left_node is None: 
			print curr.data, 
			curr = curr.right_node 
		else: 
			# point out the previous (prev) of curr 
			prev = curr.left_node 
			while(prev.right_node is not None and prev.right_node != curr): 
				prev = prev.right_node 

			# Make curr as right child of its prev 
			if(prev.right_node is None): 
				prev.right_node = curr 
				curr = curr.left_node 
				
			# fix the right child of prev
			else: 
				prev.right_node = None
				print curr.data, 
				curr = curr.right_node 
			

root = Node(4) 
root.left_node = Node(2) 
root.right_node = Node(5) 
root.left_node.left_node = Node(1) 
root.left_node.right_node = Node(3) 

Morris(root) 

⌚ Explain advantages and disadvantages of Morris Traversal?

The following are some of the benefits of employing the Morris Traversal method for inorder tree traversal:

Allows traversal of inorder trees without recursion or stacking.
Unlike when a stack is utilised for the purpose, it does not require additional space.
Recursion requires more memory and time than this method.
The parent is tracked by the node.

The Morris Traversal method for inorder tree traversal has the following drawbacks:
This results in a more complicated tree.
At any given time, only one traversal is possible.
When both children are missing from a binary tree and both node values point to their ancestors, it can be error-prone.

⌚ What exactly is a balanced tree, and why is it important?

A tree is said to be balanced when all three conditions are met:
The difference in height between the left and right subtrees is only one.
The left-hand subtree is well-balanced.
The balanced right subtree

Height-balancing criterion:
A node in a tree is height-balanced if the heights of its subtrees differ by no more than one.
A tree is considered to be height-balanced if all of its nodes are of equal height.
A balanced BST has a height of log n, where n is the number of elements in the tree. In the worst situation and in an imbalanced BST, the tree's height can reach n, making it identical to a linked list. In the worst scenario, each operation (search, insertion, and deletion) requires time O(n), which can be avoided.

⌚ Explain the difference between Binary Tree and Binary Search Tree(BST)?

⌚How can you know whether two trees are identical?

Two binary trees are similar if they have the same data and organisation. This can be performed by visiting both trees and comparing their data and arrangements.

The algorithm that will enable us to do so is as follows:
Examine the data of the root node (t1 data ==t2 data).
Check the left subtree recursively. sameTree(t1->left subtree, t2->left subtree)
Similarly, we look for the correct right subtree.
If the conditions outlined above are met, we will issue a 1

⌚ What do you mean by BST?

A binary search tree (BST) is a binary tree with a key for each internal node. A binary search tree's rule is as follows:
A key can be bigger than all the keys in a node's left subtree.
The right subtree of a node can have a key that is smaller than the subtree's other keys.
If n1 has the key 5, then every node in n1's left subtree has keys less than 5 and every node in n1's right subtree has keys greater than 5.

⌚ What is a tree's diameter?

A tree's diameter is the length of the longest path between any two nodes. The number of edges that go along a path determines its length. Remember that this node does not have to pass via the tree's root node.

⌚Explain BFS traversal?

When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and uses a queue to remember to retrieve the next vertex to start a search.

Step 1: Go to the next unexplored vertex. It should be marked as visited. Show it off. Add it to a queue.
Step 2: Remove the first vertex from the queue if no neighbouring vertex is discovered.
Step 3: Repetition of Rules 1 and 2 until the line is empty.

⌚ Explain DFS traversal?

DFS (depth–first search) is a tree or graph data structure traversal or search algorithm. Starting at the base (choosing any arbitrary node as the graph's root), one explores as far as possible along each branch before returning to the beginning.

A tree is an undirected graph with precisely one path connecting any two vertices. In other words, a tree is any acyclic connected graph. We have the following tree traversal methods:
Visit each node first, then its children.
Visit each node after its children, in reverse order.
Visit the left subtree, node, and right subtree in this order (for binary trees only).

⌚ Explain how to delete node in BST?

The Delete function is used to remove a node from a binary search tree. However, we must delete a node from a binary search tree without breaking the property of the binary search tree. A node can be deleted from a binary search tree in three different ways.

Leaf node deletion:
This is the simplest example, simply replace the leaf node with NULL and free the allotted space.
One child node deletion
Replace the node with its child in this case, then remove the child node, which now has the value to be destroyed. Simply replace it with NULL and the allotted space will be free.
Two child node deletion
In comparison to the other two situations, this one is a little more complicated. The node that is to be destroyed, on the other hand, is recursively replaced with its in-order successor or predecessor until the node value (to be removed) is placed on the tree's leaf. Replace the node with NULL and clear the allocated space after the process.

⌚ What is LCA in Binary tree how will you find it for 2 given node?

A binary tree's lowest common ancestor (LCA) is the lowest (i.e., deepest) node that has both x and y as descendants, where each node might be a descendant of itself (so if x is reachable from w, w is the LCA). In other words, the LCA of x and y is their shared ancestor that is the furthest away from the root.

In the binary tree, we can recursively locate the lowest common ancestor of nodes x and y. The trick is to locate the node in a binary tree that has one key in the left subtree and the other in the right subtree. If y is in the subtree rooted at node x, then x is the LCA; otherwise, if x is in the subtree rooted at node y, then y is the LCA.

class Solution {
public:
    TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
        //base case
        if (root == NULL || root == p || root == q) {
            return root;
        }
        TreeNode* left = lca(root->left, p, q);
        TreeNode* right = lca(root->right, p, q);

        //result
        if(left == NULL) {
            return right;
        }
        else if(right == NULL) {
            return left;
        }
        else { //both left and right child are present, we found our result
            return root;
        }
    }
};

⌚ How do you count leaf nodes in a binary tree?

If both the left and right child nodes of a node are NULL, it is considered a leaf node.
1) Return 0 if the node is NULL.
2) Otherwise, return 1 if the left and right child nodes are both NULL.
3) If not, recursively calculate the tree's leaf count using the algorithm below.
Leaf count of a tree = left subtree leaf count + right subtree leaf count

⌚ How do you make a binary search tree from a binary tree?

The rule that the left subtree should have lower key values and the right subtree should have higher key values distinguishes a binary tree from a binary search tree. The following traversal approaches can be used to achieve this:
Make a temporary array to hold the inorder traverse of the tree.
Sorting the temporary array is required. Any sorting method can be used in this situation.
Once more, traverse the tree in reverse order.
Copy the array elements to each tree node one by one.

⌚ What is height of binary tree?

The highest number of edges in a path from a leaf node to a target node is the height of a node in a binary tree. If there are no additional nodes connected to the target node, the height of that node will be 0. A binary tree's height is equal to the height of the root node in the entire binary tree. In other words, the highest number of edges from the root to the farthest leaf node determines the height of a binary tree.

🚀Conclusion

This page has reached the end of its content. You should be able to construct your own programmes with the material on this page and some practise, and little projects are highly encouraged for improving your programming skills. You won't be able to learn everything you need to know about programming in a single course it's like a marathon.

TEST YOUR KNOWLEDGE!