Binary Trees and BSTs: Traversals, Search, and Balancing

Why Binary Trees and BSTs Matter for Interviews

In the realm of software engineering interviews, Binary Trees and Binary Search Trees (BSTs) are pivotal concepts that you will encounter. These data structures are not only fundamental in computing theory but also form the basis of many complex algorithms and applications. Interviewers often use questions about these structures to assess your understanding of recursion, data organization, and efficiency in searching and modifying data. Mastering these concepts can significantly enhance your problem-solving skills and boost your confidence during technical interviews.

Prerequisites

Before diving into binary trees and BSTs, ensure you're comfortable with:

• Basic understanding of data structures (arrays, linked lists).
• Familiarity with recursion and iterative solutions.
• Basic knowledge of Big-O notation for analyzing algorithm efficiency.
• Some experience with reading and writing code in Python and JavaScript.

Binary Trees and BSTs: Traversals, Search, and Balancing

Understanding Binary Trees

A Binary Tree is a hierarchical data structure where each node has at most two children referred to as the left child and the right child.

Traversals

Traversals are a core operation in binary trees, allowing you to visit each node in a specific order.

• In-order Traversal: Visit the left subtree, the node, and then the right subtree.
• Pre-order Traversal: Visit the node, then the left subtree, and finally the right subtree.
• Post-order Traversal: Visit the left subtree, the right subtree, and then the node.

graph TD;
    A[Root] --> B[Left Child];
    A --> C[Right Child];
    B --> D[Left Subtree];
    B --> E[Right Subtree];
    C --> F[Left Subtree];
    C --> G[Right Subtree];

Code Implementation

Python Example:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def in_order_traversal(root):
    return in_order_traversal(root.left) + [root.val] + in_order_traversal(root.right) if root else []

# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(in_order_traversal(root))  # Output: [2, 1, 3]

JavaScript Example:

class Node {
    constructor(key) {
        this.left = null;
        this.right = null;
        this.val = key;
    }
}

function inorderTraversal(root) {
    return root ? [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)] : [];
}

// Example usage
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
console.log(inorderTraversal(root)); // Output: [2, 1, 3]

Binary Search Trees (BSTs)

A BST is a special type of binary tree where each node follows the property: the left subtree has values less than the node, and the right subtree has values greater than the node.

Searching in a BST

The search operation in a BST exploits its sorted property to achieve efficient search times.

Python Example:

def search_bst(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search_bst(root.right, key)
    return search_bst(root.left, key)

JavaScript Example:

function searchBST(root, key) {
    if (root === null || root.val === key) return root;
    if (root.val < key) return searchBST(root.right, key);
    return searchBST(root.left, key);
}

Complexity:

• Time: O(h) where h is the height of the tree.
• Space: O(h) due to recursion stack.