SoftwareInLevels

Understanding Binary Search Trees — Level 2

Implementation deep dive: master BST operations including insertion, search, deletion, and tree traversals with production-ready code patterns.

Author

Mr. Oz

Date

Read

8 mins

Level 2
Code implementation showing BST operations and traversal methods

Author

Mr. Oz

Date

Read

8 mins

Share

Twitter YouTube

In Level 1, we understood what BSTs are. Now let's implement them. We'll cover the core operations that make BSTs useful in real applications.

The Node Structure

Every BST node needs three things: a value and two child pointers.

# Python

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

// Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int val) { this.val = val; }

}

// C++

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

Search Operation

Searching is the fundamental BST operation. Compare and go left or right.

# Python

def search(root, target):

if not root or root.val == target:

return root

if target < root.val:

return search(root.left, target)

return search(root.right, target)

Time: O(log n) balanced, O(n) worst case | Space: O(log n) recursion stack

Insert Operation

Insertion follows the same path as search, but we create a new node when we hit a null.

# Python

def insert(root, val):

if not root:

return TreeNode(val)

if val < root.val:

root.left = insert(root.left, val)

else:

root.right = insert(root.right, val)

return root

// Java

public TreeNode insert(TreeNode root, int val) {

if (root == null) return new TreeNode(val);

if (val < root.val)

root.left = insert(root.left, val);

else

root.right = insert(root.right, val);

return root;

}

Note: Equal values typically go to the right subtree (or left, depending on implementation choice). Be consistent!

Delete Operation (The Tricky One)

Deletion has three cases based on how many children the node has:

  • No children: Simply remove the node (return null)
  • One child: Replace node with its child
  • Two children: Replace with inorder successor (smallest in right subtree) or inorder predecessor

# Python

def delete(root, key):

if not root:

return None

if key < root.val:

root.left = delete(root.left, key)

elif key > root.val:

root.right = delete(root.right, key)

else: # Found the node to delete

if not root.left:

return root.right

if not root.right:

return root.left

# Two children: find inorder successor

succ = find_min(root.right)

root.val = succ.val

root.right = delete(root.right, succ.val)

return root

# Helper: find minimum node

def find_min(node):

while node.left:

node = node.left

return node

Tree Traversals

Four main traversal patterns — each serves different purposes:

Inorder (Left → Root → Right)

Returns sorted values in a BST!

def inorder(root):

if root:

inorder(root.left)

print(root.val)

inorder(root.right)

Preorder (Root → Left → Right)

Useful for copying/serializing trees

def preorder(root):

if root:

print(root.val)

preorder(root.left)

preorder(root.right)

Postorder (Left → Right → Root)

Useful for deleting/calculation trees

def postorder(root):

if root:

postorder(root.left)

postorder(root.right)

print(root.val)

Level Order (BFS)

Visit nodes level by level

from collections import deque

def levelorder(root):

if not root: return

q = deque([root])

while q:

node = q.popleft()

print(node.val)

if node.left: q.append(node.left)

if node.right: q.append(node.right)

Operation Complexity Summary

Operation Average Worst
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Traversal O(n) O(n)

Worst case occurs when the tree becomes a linked list (completely unbalanced).

Common Pitfalls to Avoid

  • Forgetting to return values in recursive functions — Always return the (possibly modified) subtree root back up the call stack
  • Modifying tree during traversal — This can cause infinite loops or skipped nodes; collect nodes first, then modify
  • Not handling null/None cases — Always check if root exists before accessing root.val or root.left
  • Memory leaks in C/C++ — Remember to free deleted nodes, or use smart pointers in modern C++
← Level 1 Level 3 →

All Levels