Checking if a tree is balanced using recursion

Question

Implement:

bool tree_isBalanced(tree_t tree);
    // EFFECTS: returns true if tree is balanced, false otherwise

Given the following functions that you can assume to have been implemented for you:

bool tree_isEmpty(tree_t tree);
   // EFFECTS: returns true if tree is empty, false otherwise

tree_t tree_make();
   // EFFECTS: creates an empty tree.

tree_t tree_make(int elt, tree_t left, tree_t right);
   // EFFECTS: creates a new tree, with elt as it's element, left as
   //          its left subtree, and right as its right subtree

int tree_elt(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the element at the top of tree.

tree_t tree_left(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the left subtree of tree

tree_t tree_right(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the right subtree of tree

A tree is balanced if it's right subtree and left subtree are the same height for every node in the tree. The height of a tree is defined as the number of nodes that exist in a path from the root of the tree to the deepest node in the tree. A tree with only one node has a height of one and an empty tree has a height of zero. Therefore, empty trees are trivially considered perfectly balanced.

How can I deal with the recursion growing as we move down a tree?

Is your problem that you worry about the recursion depth, or that you don't know how to do the recursion? — Some programmer dude
I find it might be difficult to implement that function recursively without redirecting it to a function that returns height and checks balance at the same time, recursively. — Serge
@Serge Hmm... I noticed that in the first read of the question, then forgot it. Think I need some morning coffee (or similar substitute). :) — Some programmer dude
@JoachimPileborg I know that feeling! Sorry about that... =< — Serge

WeirdlyCheezy WeirdlyCheezy · Accepted Answer · 2012-10-19T18:08:14

It depends which aspect of recursion growth you're worried about. If you're worried about the total number of recursive calls, it is probably worth pointing out that a typical implementation here will be O(N) total calls where N is the number of tree nodes. Since the definition of height is per node, it is hard to imagine doing better than O(N).

If you're worried about maximum recursion depth, and possibly blowing out your call stack: one thing you can do is to not use the call stack at all. That is, implement the recursion as a loop acting on top of a standard stack object instead. Under the hood, this moves the bulk of the memory usage onto the heap (through dynamic reallocation of the underlying list, deque, etc.) and prevents flooding your call stack. (Note that discussion of memory usage and stack vs heap is actually C++ implementation-dependant. But, it applies to all major PC environments to the best of my knowledge).

Checking if a tree is balanced using recursion

1 Answers