You are here:

C++/Height of a tree without recursion..

Advertisement


Question
Hi,
I just want to know the program for finding the depth of a tree without any recursive functions..

Answer
The standard O(N) non-recursive algorithm for binary tree-traversal is the Morris in-order tree traversal algorithm. The same algorithm can also be used to find the height of the tree.
See: http://stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal

The other option is the classic non-recursive breadth-first-search with the help of a stack. The maximum size that the stack reaches is the depth of the tree.
See: http://discuss.joelonsoftware.com/default.asp?interview.11.526183.4  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


vijayan

Expertise

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

Experience

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.