Check if a binary tree is balanced with iterative function?

I need to implement a non-recursive function to determine if a binary tree is balanced or not.

Anyone?

Thanks!!!

Solution 1:

Assuming that by "balanced", you mean "height-balanced" in the AVL-tree sense, and you can store arbitrary information for each node,

• For each node in post-order,
  • if either child doesn't exist, assume its respective height is 0.
  • if the height of both children differs by more than one, the tree is not balanced.
  • otherwise, this node's height is the larger of both children's heights.
• If this point is reached, the tree is balanced.

One way to perform post-order traversal:

• start at the root
• loop
  • if this node's left child exists and does not have its height computed, visit its left child next.
  • else if this node's right child exists and does not have its height computed, visit its right child next.
  • else
    • compute this node's height, possibly returning early
    • if this node is not the root, visit its parent next.
• If this point is reached, the tree is balanced.