Menu
I am not sure how to determine if a tree is balanced, perfectly balanced, or neither if I have it as a picture not a code
For example if I have this tree How can I check if it's balanced, perfectly balanced, or unbalanced? and can someone give me an example of a perfectly balanced tree?
[o]
/ \
[b] [p]
\ / \
[d] [m] [r]
Clearly I can tell that the tree is unbalanced if it was something like this:
[b]
\
[d]
\
[r]
\
[c]
However, if it was something very similar to the one above I don't know how to get it
This is a perfectly balanced and balanced tree:
[k]
/ \
[A] [p]
/ \
[N] [R]
Can someone please explain it to me?
294
To check if a Binary tree is balanced we need to check three conditions : The absolute difference between heights of left and right subtrees at any node should be less than 1. For each node, its left subtree should be a balanced binary tree. For each node, its right subtree should be a balanced binary tree.
To see if a binary tree is a binary search tree, check: If a node is a left child, then its key and the keys of the nodes in its right subtree are less than its parent's key. If a node is a right child, then its key and the keys of the nodes in its left subtree are greater than its parent's key.
Creating a Balanced BST Since we need the tree to be balanced, we must put the middle value as the root. After that, we can add the values before the middle to the left of the tree. Therefore, all smaller values will be added to the left subtree.
Every complete binary tree is balanced but not the other way around. As implies, in a complete tree, always the level difference will be no more than 1 so it is always balanced.
A perfectly balanced tree should look like this:
[ R ]
/ \
[a] [b]
/ \ / \
[c] [d] [e] [f]
Balanced: You can say it is balanced because the height of the left and right subtrees from every node differ by 1 or less (0 in this case),
Perfect: You can say it is perfect because the number of nodes is equal to 2^(n+1)-1 with n being the height of the tree, in this case (2^3) - 1 = 7
In your examples the 1st tree is balanced, but not perfect, the second is not balanced nor perfect. The third one is balanced because the depth for the left and right subtree on every node differ on 1 or less, but it is not perfect because the number of nodes is 5 when it should be 7 according to the perfect tree equation.
EDIT:
Regarding your lasts comments, the fact that you got it in an exam doesn't mean the answer was right in every sense. The notion of perfect tree is related to the notion of completeness, a complete tree is sometimes called a "perfect" tree, and it means the number of children for every node except the leafs is 2 what i gave you is an equation to calculate it. The third tree is balanced because what matters is the depth of the left and right subtrees for every node, not the number of children in the left and right subtrees. In this case from node A the depth of left subtree is 0 and the depth of right subtree is 0 -> 0 - 0 = 0, from P both depth are 1 -> 1 - 1 = 0 and from the root the depth from the left subtree is 1 and from the right subtree is 2 -> 2 - 1 = 1 <- it is balanced, since the difference should be 1 or less.
Hope it helps!
73
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
