Mastering Interview Problems with Binary Search Trees

Introduction to the Lesson

Welcome to today's lesson! In this practice-based session, we'll unravel the mysteries of Binary Search Trees (BSTs). We will focus on two well-known interview problems related to binary trees. Solving these problems will solidify your understanding of trees and provide you with hands-on experience that will be invaluable during future job interviews. Think of this as mock interviews before the real one! So, let's put on our problem-solving hats and dive right in!

Problem 1: Checking the Balance of a Binary Tree

Here is the first problem: we need to write a function that checks if a binary tree is balanced. The tree is balanced if for each vertex, the height of the left subtree differs from the height of the right subtree by at most 1. Note that although this lesson focuses on BSTs, this balance check applies to any binary tree, since it depends only on structure and not on node values.

Problem 1: Problem Actualization

You might wonder, "Why do we need to do this?". Well, this problem frequently appears in job interviews because checking the balance of a tree optimizes search operations. Interestingly, consider trying to balance on one foot. If the weight on your left and right sides is not equal, you'll topple over, right? Similarly, a binary tree is considered balanced when the left and right sides are equal, or at least the difference is no more than one. Isn't that fascinating?

Problem 1: The Naive Approach

So, let's discuss the naive approach to solving this problem. One could start by calculating the heights of all subtrees and then checking whether the heights of each node's left and right subtrees differ by no more than one. While this approach is functional, it is inefficient since it involves traversing the entire tree multiple times and making duplicate calculations.

Problem 1: Efficient Approach Explanation

But don't worry, there's a more efficient way! Instead of traversing the tree multiple times, we can use recursion to do it all in one sweep. We calculate the heights of the subtrees while simultaneously checking the balance condition. So, essentially, we're hitting two birds with one stone!

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

def is_balanced(root) -> bool: # returns (height, is_balanced) def check_balance(node) -> tuple[int, bool]: if node is None: return 0, True left_height, left_balanced = check_balance(node.left) if not left_balanced: return -1, False right_height, right_balanced = check_balance(node.right) if not right_balanced: return -1, False height = max(left_height, right_height) + 1 is_balanced = abs(left_height - right_height) <= 1 return height, is_balanced height, balanced = check_balance(root) return balanced

def kth_smallest(root, k): # The number of nodes in the left subtree of the root left_nodes = count_nodes(root.left) if root else 0 # If k equals the number of nodes in the left subtree plus 1, # the root value is the k-th smallest element. if k == left_nodes + 1: return root.val # If k is less than or equal to the number of nodes in the left subtree, # the k-th smallest must be in the left subtree. elif k <= left_nodes: return kth_smallest(root.left, k) # Otherwise, the k-th smallest is in the right subtree, # with its rank adjusted by subtracting the left subtree size and the root. else: return kth_smallest(root.right, k - 1 - left_nodes) def count_nodes(root): if not root: return 0 return 1 + count_nodes(root.left) + count_nodes(root.right)

Introduction to the Lesson

Problem 1: Checking the Balance of a Binary Tree

Problem 1: Problem Actualization

Problem 1: The Naive Approach

Problem 1: Efficient Approach Explanation

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building

Problem 2: Identify the K-th Smallest Element in a Binary Search Tree

Problem 2: Actualization

Problem 2: Naive Approach

Problem 2: Efficient Approach

Problem 2: Solution Implementation

Lesson Summary

Practice Exercises