Mastering Trees & BSTs: Traversals, Height & Key Operations

In partnership with

Welcome to the Nullpointer Club Newsletter!

If you've attended any coding interviews or taken any interviews for entry-level developers, you've probably realized that trees are one of the most frequently tested topics. From binary trees to binary search trees (BSTs), these hierarchical data structures are fundamental to solving complex problems efficiently.

Today, we’re diving into Tree Traversals, BST Height, and Basic Operations—all the essentials you need to level up your understanding them.

Why Are Trees & BSTs Important?

Trees are widely used in various real-world applications such as:

• Databases (e.g., B-Trees in indexing)

• File systems (hierarchical directory structures)

• AI & Machine Learning (decision trees, game trees)

• Networking & Routing (spanning trees, trie structures)

BSTs, in particular, provide efficient search, insert, and delete operations—making them essential for fast data retrieval.

Understanding Tree Traversals

Traversal is the process of visiting each node in a tree. The three main types of tree traversals are:

1. Inorder Traversal (Left -> Root -> Right)

Used for: Sorting BSTs (results in sorted order)

# Inorder Traversal (Recursive)
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

2. Preorder Traversal (Root -> Left -> Right)

Used for: Creating a copy of the tree, prefix expression evaluation

# Preorder Traversal
def preorder(root):
    if root:
        print(root.val, end=' ')
        preorder(root.left)
        preorder(root.right)

3. Postorder Traversal (Left -> Right -> Root)

Used for: Deleting a tree, postfix expression evaluation

# Postorder Traversal
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val, end=' ')

For larger trees, iterative traversals using stacks or queues (for level-order traversal) might be required.

Height of a BST

The height of a BST is the longest path from the root to a leaf node.

Time Complexity: O(n) (for unbalanced trees)

def height(root):
    if not root:
        return -1
    return 1 + max(height(root.left), height(root.right))

A balanced BST (like AVL Trees) has O(log n) height, improving search efficiency.

Basic BST Operations

1. Insertion in a BST

Time Complexity: O(log n) (balanced), O(n) (unbalanced)

def insert(root, key):
    if not root:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

2. Searching in a BST

Time Complexity: O(log n)

def search(root, key):
    if not root or root.val == key:
        return root
    return search(root.left, key) if key < root.val else search(root.right, key)

3. Deleting a Node in a BST

Handles three cases:

1. Node has no children → Simply remove it

2. Node has one child → Replace it with its child

3. Node has two children → Replace with inorder successor

def deleteNode(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        temp = findMin(root.right)  # Find inorder successor
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

Common Questions on Trees & BSTs and How to Approch Them

Here are some commonly asked questions:

Q1. Given a BST, check if it’s a valid BST. 

Use an inorder traversal and verify if values are in sorted order.

Q2. Find the Lowest Common Ancestor (LCA) of two nodes in a BST. 

Start from the root and navigate based on values.

Q3. Convert a BST to a sorted doubly linked list. 

Use inorder traversal and modify pointers.

Q4. Find the kth smallest element in a BST. 

Use inorder traversal and track the count.

Mastering trees and BSTs is essential for upskilling and acing coding interviews. By understanding traversal techniques, calculating tree height, and implementing fundamental operations like insertion, searching, and deletion, you'll be well-equipped to tackle challenging problems. Keep practicing with variations of questions and focus on optimizing your solutions. With persistence, you'll develop a strong foundation in data structures, paving the way for success in your coding journey.

Engineering Job Openings To Look Out For

• Software Development Associate : United Nations Development Programme (UNDP)

• Software Engineeer : DHL Supply Chain

• Backend Developer : Truelancer.com

Happy coding,

The Nullpointer Club Team