Cheap and Secure Web Hosting Provider : See Now

What is the order of this traversal method?

, , No Comments
Problem Detail: 

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.

Asked By : samol

Answered By : babou

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback