Binary Tree Traversal

A Tree is said to be a Binary Tree if all of its nodes have atmost 2 children. That is, all of its node can have either no child, 1 child or 2 child nodes.

Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which is linear data structures and have only one logical way to traverse the elements, trees can be traversed in different ways. Following are the generally used ways for traversing trees.

The tree traversal techniques given below:

  1. Inorder Traversal (<left><root><right>)
  2. preorder Traversal (<root><left><right>)
  3. Postorder Traversal (<left><right><root>)

Let’s see the example:

Binary Tree

1.Inorder Traversal: Process all nodes of a tree by recursively processing the left subtree, then processing the root, and finally the right subtree. Also known as symmetric traversal.

Algorithm:

 1. Traverse the left subtree, i.e., 
call Inorder(left->subtree)
2. Visit the root.
3. Traverse the right subtree, i.e.,
call Inorder(right->subtree)

Inorder = 4 2 5 1 6 3 7

2. Preorder Traversal: Process all nodes of a tree by processing the root, then recursively processing all subtrees. Also known as prefix traversal.

Algorithm:

1. Visit the root.
   2. Traverse the left subtree, i.e., 
      call Preorder(left-subtree)
   3. Traverse the right subtree, i.e., 
      call Preorder(right-subtree) 

Preorder = 1 2 4 5 3 6 7

3. Postorder Traversal: Process all nodes of a tree by recursively processing all subtrees, then finally processing the root. Also known as postfix traversal.

Algorithm:

1. Traverse the left subtree, i.e., 
call Postorder(left-subtree)
2. Traverse the right subtree, i.e.,
call Postorder(right-subtree)
3. Visit the root.

Postorder = 4 5 2 6 7 3 1

Hope you guys understand what is binary tree and its traversing techniques.

In the next blog we will see the implementation of these techniques using both methods i.e iterative and recursive in java.

So till then Bye Bye…!

Happy Coding..!

Thank You…!



Categories: HackerRank Questions, Interview, JAVA

Tags: , , , , , , , ,

4 replies

Trackbacks

  1. Tree: Inorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  2. Tree: Preorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  3. Tree: Postorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  4. Vertical Order Traversal In Binary Tree – THE NUCLEAR GEEKS

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: