Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Tree Traversals

There are mul­ti­ple ways to in which you can tra­verse a tree. In this arti­cle we will see these tra­ver­sals in detail. If you are new to trees then I would rec­om­mend that you pay close atten­tion to this arti­cle because you will be solv­ing almost all the prob­lems on tree by using one or more of these traversals.

Here we will dis­cuss the recur­sive approach, we will have sep­a­rate posts for Iter­a­tive or Non-recursive approach.

Tra­ver­sals:

Tree Traversals

Tree Tra­ver­sals

 

In every tra­ver­sal we visit the tree in cer­tain order. lets  dis­cuss them in detail.

Pre­order Tra­ver­sal: ( Read about non-recursive approach of Pre­order Tra­ver­sal)

  • Visit the root.
  • Visit the left-subtree.
  • Visit the right-subtree.

Inorder Tra­ver­sal: ( Read about non-recursive approach of Inorder Tra­ver­sal)

  • Visit the left-subtree.
  • Visit the root.
  • Visit the right-subtree.

Pos­torder Tra­ver­sal: ( Read about non-recursive approach of Pos­torder Tra­ver­sal)

  • Visit the right-subtree.
  • Visit the left-subtree.
  • Visit the root.

Click here to read about Breadth-First Search and Depth-First Search.

Code:

Output:

Inorder Traversal:4 2 5 1 6 3 7
Preorder Traversal:1 2 4 5 3 6 7
Postorder Traversal:7 6 3 5 4 2 1

You may also like...

  • Fuen Wu

    As per the expla­na­tion ‚it seems that the code for pos­tOrder­Recur­sive is not right ‚it visit right sub­tree firstly.

    • tuto­ri­al­hori­zon

      Thanks Fuen, changed the explanation.

  • Shilpa

    Post order tra­ver­sal Algo­rithm is not cor­rect.
    It should be as fol­lows–
    1. Visit the left sub­tree
    2. Visit the right sub­tree.
    3. Then visit the root

    • kosciCZ

      +1, Fuen Wu propably meant that the code is wrong, the cor­rect order of Post order indeed is Left Right Root.