Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Traversals
2.1.
Preorder
2.2.
Postorder
2.3.
Inorder
2.4.
Level Order Traversal
3.
Algorithms
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Traversing Binary Trees

Author Saksham Gupta
1 upvote
gp-icon
Discrete Mathematics
Free guided path
3 chapters
31+ problems
gp-badge
Earn badges and level up

Introduction

Binary trees are an all-time favorite topic for coding interviews. Thus, it is important to master such a topic. There are a large number of questions out there on binary trees, but if you get the hold of the topic right, you are good to go. Before solving, we should be aware of the traversals. In this blog, we will be discussing the same. 

Traversals

Traversing a tree involves visiting all of its nodes. To traverse binary trees, there are three typical approaches. The following are :

  1. Preorder Traversal
  2. Postorder Traversal
  3. Inorder Traversal
  4. Level Order Traversal

Preorder

Algorithm Preorder(tree)

1. Go to the root.

2. Go to the left subtree and call Preorder (left-subtree)

3. Navigate to the appropriate subtree, i.e., call Preorder (right-subtree)

Postorder

Algorithm Postorder(tree)

1. Call Postorder to traverse the left subtree (left-subtree)

2. Navigate to the appropriate subtree, i.e., call Postorder (right-subtree)

3. Go to the root.

Inorder

Algorithm InOrder (tree)

1. Call In order to traverse the left subtree (left-subtree)

2. Go to the root.

3. Navigate to the appropriate subtree, i.e., call Inorder (right-subtree)

Level Order Traversal

Printing the nodes of the tree level-wise is known as level order traversal.

 

Source: source

 

 

Let's see some of the algorithms now.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 -

 

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

Previous article
Introduction to Trees
Next article
Binary Search Trees
Guided path
Free
gridgp-icon
Discrete Mathematics
3 chapters
31+ Problems
gp-badge
Earn badges and level up
Live masterclass