Traversing Binary Trees

Algorithms

Q1. When the tree's inorder and preorder traversal are known, Your task is to draw a unique binary tree:

Example

Inorder Traversal : [4, 2, 7, 1, 3]

Preorder Traversal: [1, 2, 4, 7, 3]

Tree

Source: source

Steps: 

1. The first node in the binary tree's ordering is the root. Draw the tree's root using this.
    
2. To identify the root node's left child, utilize inorder traversal to find the nodes in the binary tree's left subtree. (The nodes of the left subtree are all those nodes in the inorder traversal that are left to the root node.) The left child of the root is then found by selecting the first node in the left subtree's preorder traversal. Draw the child on the left using this.
    
3. Similarly, utilize inorder traversal to locate the nodes in the binary tree's right subtree. The right child is then acquired by selecting the first node in the right subtree's preorder traversal. Draw the right child using this.
    
4. Steps 2 and 3 should be repeated for each successive node until none of them have been visited in the preorder. Finally, we have a one-of-a-kind unique tree.
    

Q2. When both inorder and postorder traversal of the tree is given, Your task is to draw a unique binary tree:

Example

Inorder = [9, 3, 15, 20, 7] 

Postorder = [9, 15, 7, 20, 3].

Tree

Source: source

Steps: 

1. The root of the binary tree is the last node in its postorder, as we know. Make a drawing of the tree's root using it.
    
2. To discover the right child of the root node, first, find the nodes in the right subtree of the binary tree using inorder traversal. (The nodes of the right subtree are all the nodes in the inorder traversal that are right to the root node.) The right child of the root is then obtained by selecting the last node in the right subtree's postorder traversal. Draw the right child using this.
    
3. Similarly, use inorder traversal to identify the nodes in the binary tree's left subtree. The left child is then obtained by selecting the last node in the left subtree's postorder traversal. Make a drawing of the child on the left using this.
    
4. Repeat steps 2 and 3 with each successive node until no node in the postorder has been visited. We get a unique tree after visiting the last node.
    

Q3. Your task is to make a binary tree out of a general tree:

Example

Source: source

Tree

Source: source

Steps: 

1. The root of the tree is also the root of the binary tree, starting from the root node.
    
2. The left child C1 of the root node in the binary tree is the first child C1 of the root node in the tree (from left), and the sibling of C1 is the right child of C1, and so on.
    
3. Repeat Step 2 for each new node. 
    

Check out this problem - Mirror A Binary Tree

FAQs

1. What are Binary Trees?
   If every node has at most two child nodes, the tree is termed a binary tree. A left pointer, a right pointer, and a data element make up a binary tree node. A valid binary tree is also an empty binary tree (one with 0 nodes).
    
2. What is a generic tree?
   A generic tree, often known as an n-ary tree, is a tree data structure in which each node can have up to n children, with n being an integer number.
    
3. What are some of the advantages of using binary trees?
   Data is inserted and deleted faster than linked lists and arrays. A hierarchical method of storing data is faster than a linked list, and it also denotes the structural relationship that exists in the data.
    
4. What is the need for balancing Binary Trees?
   A balanced binary tree reduces the amount of time it takes to search through the tree. In the worst scenario, the search time complexity of a balanced binary tree is O(log n), whereas, in the best situation, it is O(n), where n is the number of nodes. For huge trees, keeping a balanced tree is advantageous.
    
5. Is there any other Data Structures and Algorithms content in Coding Ninjas Studio?
   Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.

Key Takeaways

In this article, we have extensively discussed how we can traverse binary trees. We saw all 4 methods as well as saw a few algorithms. We hope that this blog has helped you enhance your knowledge of traversing binary trees, and if you would like to learn more, check out our articles on Library. 

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

Do upvote our blog to help other ninjas grow. Happy Coding!”