Re: finding height of a BST by iteration

subramanian100in@xxxxxxxxx, India wrote:

I know the Inorder, Preorder and Postorder traversal of a BST by
iteration.
Still I do not know how to calculate the height of a BST by iteration.

If you can traverse the tree in any order (with or without recursion)
then you can find the maximum height of the tree as you do so.

Keep a count, current_depth, of how deep you are in the tree at any one
step. Start with zero, increment current_depth whenever you move to a
node's children, decrement it whenever you step back from a node to its
parent. Keep a separate variable holding the maximum value of
current_depth. After you have completed the tree traversal, the
maximum will hold the height/depth of the tree.

-- chris
.

Relevant Pages

  • Re: ActiveTreeModel (Beta)
    ... Currently the Tree object uses a map internally, ... the formalities behind the design of the TREE class in Eiffel are ... I very much like Smalltalk's approach to iteration. ... Conversation: ActiveTreeModel (Beta) ...
    (comp.lang.smalltalk.dolphin)
  • Re: ActiveTreeModel (Beta)
    ... Currently the Tree object uses a map internally, ... the formalities behind the design of the TREE class in Eiffel are ... I very much like Smalltalk's approach to iteration. ... Conversation: ActiveTreeModel (Beta) ...
    (comp.lang.smalltalk.dolphin)
  • Re: level order traversal of binary tree
    ... queue proportional to the sizeo of the tree. ... int depth) ... visists more than twice as many nodes as in the previous iteration. ... traverse each node twice on average. ...
    (comp.lang.c)
  • Re: ActiveTreeModel (Beta)
    ... Currently the Tree object uses a map internally, ... implementation of TreeModel. ... the root. ... convinced by the idea of a collection knowing the state of an iteration over ...
    (comp.lang.smalltalk.dolphin)
  • Erroneous Post
    ... Conversation: ActiveTreeModel (Beta) ... Currently the Tree object uses a map internally, ... It may help to consider that, despite its name, a TreeModel is ... the iteration method. ...
    (comp.lang.smalltalk.dolphin)