Trees – Simple Operations and Traversal.

Trees – Simple Operations and Traversal.

This article is a simple summary of most frequently performed operations over tree data structure. As an enterprise Java developer I don’t usually deal with traverse or other calculations with trees, There are already well designed and tested libraries to do the job. However, interviewers usually like to ask these questions and give you task or two – to be done on paper- that involves these operations.

For basic definitions of trees check my previous article. 

 

Trees Nodes
Tree Nodes

 

This factory creates the simple tree in the picture: 

Find the high of tree.

Pre-order tree traversal

Traversing a tree means visiting its node, to find if some value exists in that tree.

Pre-order traversing means do something with the current node (visit the node),display the value of it for example , traverse the left sub-tree then the right sub-tree recursively.

Algorithm: 

  • Display the data part of the root (or current node).
  • Traverse the left subtree by recursively calling the pre-order function.
  • Traverse the right subtree by recursively calling the pre-order function.

Post-order

The root node is visited last. First left subtree is traversed, then right subtree and finally root.

Algorithm: 

  • Traverse the left subtree by recursively calling the post-order function.
  • Traverse the right subtree by recursively calling the post-order function.
  • Display the data part of the root (or current node).

Outcome: 7 > 0 > 5 > 8 > 7 > 1 > 3 > 5 >

In-order

Algorithm:

  • Traverse the left subtree by recursively calling the in-order function.
  • Display the data part of the root (or current node).
  • Traverse the right subtree by recursively calling the in-order function. 

Outcome: 8 > 7 > 5 > 0 > 7 > 5 > 3 > 1 >

Facebooktwittergoogle_pluslinkedinFacebooktwittergoogle_pluslinkedin

Leave a Comment