1,105,226 Community Members

Function to determine if the binary search tree is perfectly balanced

Member Avatar
ariel930
Newbie Poster
6 posts since Oct 2012
Reputation Points: 11 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hello again.I recently have been doing a assignment which asks us to write a function to check whether a tree is perfectly balanced.I know the concept of Perfectly balanced tree but I just cant make out how to write this function.Any help in right direction will be highly welcome.

Member Avatar
ken_taiken
Newbie Poster
15 posts since Sep 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 4 [?]
Skill Endorsements: 0 [?]
 
0
 

You can modify and use DFS. For every node you can check if the depth of the two subtrees coming under it is equal or not.

Member Avatar
deceptikon
Eternally Awesome
4,662 posts since Jan 2012
Reputation Points: 1,339 [?]
Q&As Helped to Solve: 678 [?]
Skill Endorsements: 104 [?]
Administrator
Featured
 
0
 

By perfectly balanced do you mean a complete tree? A full tree? Merely a height balanced or weight balanced tree? The algorithm is different for each. Typically what's meant is height balance, or what would be the desired end structure maintained an AVL tree.

A recursive algorithm presents itself immediately when you think about measuring the height of each subtree and comparing them:

is_balanced(tree)
    balanced = true
    height_diff = 0

    if not empty(tree)
        balanced = is_balanced(tree.left) and is_balanced(tree.right)
        height_diff = abs(height(tree.left) - height(tree.right))
    end if

    return empty or (balanced and height_diff <= 1)
Member Avatar
ariel930
Newbie Poster
6 posts since Oct 2012
Reputation Points: 11 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Our question says the following definition: A tree is perfectly balanced if on each level there are 2 power n nodes except for last level.

Member Avatar
deceptikon
Eternally Awesome
4,662 posts since Jan 2012
Reputation Points: 1,339 [?]
Q&As Helped to Solve: 678 [?]
Skill Endorsements: 104 [?]
Administrator
Featured
 
0
 

Well, you could derive a solution directly from the wording of the definition. First count the number of nodes to get a value for n, then determine the depth of the tree so you know what the last level is, finally do a level order traversal and check at the end of each level whether the size is 2^n or it's the last level.

This breaks the problem down into three smaller problems:

  1. Counting the nodes in a tree.
  2. Finding the depth of a tree.
  3. Performing a level order traversal and counting nodes on each level.
Member Avatar
ariel930
Newbie Poster
6 posts since Oct 2012
Reputation Points: 11 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
1
 

Thank you so much you all for your kind relpies.I have finished making my function.My function does the following:

1)Counts the total number of nodes of the tree.
2)Counts the numbers of nodes on the last level.
3)Determine the depth of the tree.
4)Total nodes-last level nodes.
5)Compare the answer to 2 pow (height-1) -1.
And it worked.

Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

Also note that you might be able to skip transversal if the number of nodes isn't a power of 2. If it is, then you have to transverse just to make sure it fits the definition.

Member Avatar
yde
Newbie Poster
3 posts since Apr 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Using your definition of a perfectly balanced tree (I would call it an optimally packed tree), I think the following algorithm would work. If I'm wrong please let me know.

Traverse each path measuring its length.
Keep track of the longest and shortest paths measured.
If, at any time during the scan, the difference between longest and shortest
is greater than 1, the tree is not balanced.

If the tree is perfectly balanced you'll have to traverse the whole tree but if it's unbalanced you won't.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: