0
$\begingroup$

Please see below pseudo-code for finding the max-height of a b-tree

maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e., 
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e., 
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right 
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

My guess is that this is post-order traversal.

Because we are calculating the height of the left tree and then the right tree and in the end, we find the max(left_tree_height, right_tree_height) to figure out the max height of the root node.

$\endgroup$
2
$\begingroup$

This is a depth first recursive binary tree traversal.

Such a traversal may be qualifed as pre-order, in-order, or post-order if you do some specific action on each node, before the first recursive call, between the two recursive calls, or after the second recursive call.

Actually, you can have several actions to perform, some in pre-order, some in in-order, and some in post-order.

In your case, you have to collect and combine the information from the two subtrees, and that is necessarily in post-order. But it is just using terminology, which I see as moderately meaningful in this context.

These concept often suppose an order of the daughters of a node, but this is largely irrelevant here. You can process your subtrees in any order, left first or right first. I guess that is also why I am a bit reluctant to make this postorder distinction. The pre-order, in-order, post-order distinction assumes you are exploring depth first from left to right.

They also correspond to distinct linear notations for representing binary trees, where nodes are labeled differently from leaves: prefix, infix and postfix.

$\endgroup$
  • $\begingroup$ Good points all. As an additional note, the distinction between the orders (up to order of the children) can be important when you do things like annotating parse trees in a compiler; some concepts flow top-down (--> pre-order), other things bottom-up (--> post-order). $\endgroup$ – Raphael Jun 19 '15 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.