Hi,
I am trying to write code to test if a tree is balanced.
The function will take a pointer to the root node of the tree and will have to figure out if the tree is balanced.
The tree is a normal binary tree.
Any ideas/code?
This is a discussion on Code to test if a tree is balanced within the C Programming forums, part of the General Programming Boards category; Hi, I am trying to write code to test if a tree is balanced. The function will take a pointer ...
Hi,
I am trying to write code to test if a tree is balanced.
The function will take a pointer to the root node of the tree and will have to figure out if the tree is balanced.
The tree is a normal binary tree.
Any ideas/code?
A binary tree if perfectly balanced if the height of the left child is the same as the height of the right child. Normally, a balanced tree algorithm will relax this condition so that the height of the left and right child can differ by at most 1.
Whatever "balanced" means to you, all you need is a recursive function to calculate the height of a given node. Then you can recursively check that every node in the tree is balanced. This will be very inefficient though.
Look up an implementation of an AVL tree if your not sure how to implement the recursion.
gg