Interview Question
0of 4 votesHow to iteratively verify if a BST is balanced?
Country: United States
Sorry, didn't see the problem clearly. If it must be iterative, we can use the nonrecursive post-order traversal algorithm. The code may be like this:
class Node {
public:
int data;
int height;
Node* left;
Node* right;
Node(int d) : data(d), height(-1), left(NULL), right(NULL) {}
~Node() {
if (left) delete left;
if (right) delete right;
left = right = NULL;
}
};
bool IsBalanced(Node* r) {
if (!r) return true;
std::stack<Node*> s;
Node* cur = r;
Node* pre = NULL;
while (cur || !s.empty()) {
while (cur) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
if (!cur->right || cur->right == pre) {
if (!cur->right) {
if (!cur->left) {
cur->height = 1;
} else {
if ((cur->left)->height > 1) return false;
cur->height = cur->left->height + 1;
}
} else {
int lheight = cur->left->height;
int rheight = cur->right->height;
if (abs(lheight - rheight) > 1) return false;
cur->height = 1 + (lheight > rheight ? lheight : rheight);
}
// visit this node
//std::cout << cur->data << std::endl;
s.pop();
pre = cur;
cur = NULL;
} else {
cur = cur->right;
}
}
return true;
}
If the tree node's content can not be modified, we can copy the tree first, and then traverse the new tree.
The time complexity is O(n), space complexity is also O(n).
@nobrainer
You first need to define what 'balanced' BST means. Does it mean the left and subtrees are of equal height? or can be off by some constant number? or of equal size?
In order to iteratively traverse a recursively defined structure like a tree, we can make use of auxiliary stack(s) or queue(s) to get the desired output. But the problem definition needs to be precise first.
I think the 2 most common definitions of balanced I've seen are
1) The height difference between any two leaves is at most 1
2) The height of the tree is at most 2 * log(N), where N is the number of elements in the tree.
In either case, we can use a Breadth First Search and record the heights of the nodes in the tree. For case 1 we want the minimum and maximum heights of the tree and for case 2 we only want the maximum.
If balanced means that all the leaves must be at the same level, we can traverse the tree using BFS. BFS runs in phases encountering nodes at a particular level in each phase. If the tree is balanced, BFS will encounter all the leaves in the same phase. It is however easy to check whether the leaves of the left and right subtrees are off by 1.
The code below shows an iterative version and the recursive version.
Some warning about some of the snippets above, sub trees can be balanced but it does not necessarily mean that the three is balanced. (e.g. if left is balanced but of height 8 and right is balanced but of height 6, overall tree is not balanced if the definition of balanced is "a tree is balanced if two leaf nodes don't differ in height by more than one").
# -*- coding: utf-8 -*-
"""Solve the balanced tree question.
Original question from Interview Cake:
Classes and functions to check if a tree is balanced.
Write a function to see if a binary tree is "superbalanced"
(a new tree property we just made up).
A tree is "superbalanced" if the difference between
the depths of any two leaf nodes is no greater than one.
"""
from unittest import TestCase, skip, main as unittest_main
class BinaryTreeNode:
"""Define Binary Tree Node class."""
def __init__(self, value, left=None, right=None):
"""Init the class
:param value: the value for the node
"""
self.value = value
self.left = left
self.right = right
self.visited = False
self.height = 0
def insert_left(self, value):
"""Insert a node with the value in the left part of the tree."""
self.left = BinaryTreeNode(value)
return self.left
def insert_right(self, value):
"""Insert a node with the value in the right part of the tree."""
self.right = BinaryTreeNode(value)
return self.right
def is_balanced_rec(root_node):
"""Check if the tree is balanced.
:return: pair with height and if the tree at
the node level is balanced.
"""
if root_node is None:
return (0, True)
right_height, is_right_balanced = is_balanced_rec(root_node.right)
left_height, is_left_balanced = is_balanced_rec(root_node.left)
return (
max(left_height, right_height) + 1,
abs(left_height - right_height) <= 1
and is_right_balanced and is_left_balanced
)
def is_balanced(root_node):
"""Check if the tree is balanced.
:return: if the tree is balanced or not
"""
height, is_balanced = is_balanced_rec(root_node)
return is_balanced
def is_balanced_iterative(root_node):
"""Check if the tree is balanced.
:return: if the tree is balanced or not
"""
nodes = list()
current_nodes = list()
current_nodes.append(root_node)
while len(current_nodes) != 0:
node = current_nodes.pop()
has_left = node.left and not node.left.visited
has_right = node.right and not node.right.visited
if has_left or has_right:
# the node has at least one child we push it back
# to the queue in order to visit it after visitin
# the child(ren)
current_nodes.insert(0, node)
if has_left:
current_nodes.append(node.left)
if has_right:
current_nodes.append(node.right)
else:
# update the current node if both its children
# have been visited or if the node is a leaf
right_height = node.right.height if node.right else 0
left_height = node.left.height if node.left else 0
if abs(left_height - right_height) > 1:
return False
node.height = max(left_height, right_height) + 1
node.visited = True
return True
class TestIsBalanced(TestCase):
"""Test cases for the is_balance method."""
def setUp(self):
"""Creates test trees before all the tests."""
self.balanced_tree_node = BinaryTreeNode(
'A',
BinaryTreeNode(
'B',
BinaryTreeNode('D')
),
BinaryTreeNode(
'C',
BinaryTreeNode(
'E',
BinaryTreeNode(
'G'
)
),
BinaryTreeNode('F')
)
)
self.unbalanced_tree_node = BinaryTreeNode(
'A',
BinaryTreeNode(
'B',
BinaryTreeNode('D')
),
BinaryTreeNode(
'C',
BinaryTreeNode(
'E',
BinaryTreeNode(
'G'
)
)
)
)
def test_is_balanced_for_balanced_tree(self):
"""Test is balanced.
Should return true for a balance tree
"""
self.assertTrue(is_balanced(self.balanced_tree_node))
def test_is_balanced_for_unbalanced_tree(self):
"""Test is balanced.
Should return true for a balance tree
"""
self.assertFalse(is_balanced(self.unbalanced_tree_node))
def test_is_balanced_iterative_for_bt(self):
self.assertTrue(is_balanced_iterative(self.balanced_tree_node))
def test_is_balanced_iterative_for_ubt(self):
self.assertFalse(is_balanced_iterative(self.unbalanced_tree_node))
if __name__ == '__main__':
unittest_main()
record the height of the tree when you traverse the tree recursively
- mwxjmmyjfm September 08, 2013class Node { public: int data; Node* left; Node* right; Node(int d) : data(d), left(NULL), right(NULL) {} ~Node() { if (left) delete left; if (right) delete right; left = right = NULL; } }; bool IsBalanced(Node* r, int& height) { if (!r) { height = 0; return true; } int rheight = 0; int lheight = 0; if (!IsBalanced(r->left, lheight)) { return false; } if (!IsBalanced(r->right, rheight)) { return false; } if (abs(lheight - rheight) > 1) { return false; } height = 1 + (lheight > rheight ? lheight : rheight); return true; }