In pseudo code a Function to test balanced tree???

Question

In pseudocode can someone show me a function test(tree) that returns TRUE when a binary tree is perfectly balanced and that returns FALSE otherwise.

Thank You.

Answer 1

Do it like a regular tree traversal, but pass an int to keep track of current depth and (by reference) a vector of ints to make a list of leaf nodes' depths.

// t is the current node

// depth is t's distance from the root

// leafDepths stores the depths of each leaf node

test(TreeNode t, int depth, vector<int> leafDepths) {

if (t has no children) { // this is a leaf

leafDepths.add(depth)

}

if (t has left-side child) {

test(t.left, depth + 1, leafDepths)

}

if (t has right-side child) {

test(t.right, depth + 1, leafDepths)

}

}

Call this, passing in the root of the tree, a depth of 0 and an empty vector<int>. At the end, the vector contains the depths of every leaf in the tree. If the smallest and largest values in the vector differ by more than 1, the tree is unbalanced.