Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 2 vote

record the height of the tree when you traverse the tree recursively

``````class 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;
}``````

Comment hidden because of low score. Click to expand.
0

Recursive solution is obvious. How about iterative ones.

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Define balanced.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

balanced means the difference between the heights of the two subtrees of any node never differ more than one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/

use this to calculate of height of root->left subtree and root->right subtree separately..
check if the difference is 0 or +/- 1, then balanced
else unbalanced

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

There are recursive procedures already, why do we need iterative ones?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.