Understanding Trees, Binary Search Trees, and Finding the Lowest Common Ancestor

In the world of computer science, data structures are the building blocks of efficient algorithms. One of the most fundamental and versatile data structures is the Tree.

This post will take you on a journey from the basics of trees to a specific type called a Binary Search Tree (BST), explore common algorithms used with them, and finally, solve a classic problem: finding the Lowest Common Ancestor of two nodes in a BST.

What is a Tree?

In computer science, a Tree is a hierarchical data structure that consists of nodes connected by edges.

Unlike linear data structures like arrays or linked lists, trees are non-linear and are used to represent hierarchical relationships.

Key Terminology:

Node: The fundamental part of a tree that stores data.
Edge: The connection between two nodes.
Root: The topmost node in a tree. It's the only node that doesn't have a parent.
Parent: A node that has a child node.
Child: A node that has a parent node.
Leaf: A node that does not have any children.
Subtree: A tree consisting of a node and its descendants.
Depth: The length of the path from the root to a specific node.
Height: The length of the longest path from a specific node to a leaf.

Trees are used in various applications, such as file systems, organization charts, and even in parsing expressions in compilers.

Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a special type of binary tree where the nodes are ordered in a specific way.

This ordering makes operations like searching, insertion, and deletion very efficient.

A binary tree is a BST if it satisfies the following properties:

The left subtree of a node contains only nodes with keys lesser than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

This structure ensures that for any given node, all the values in its left subtree are smaller, and all the values in its right subtree are larger.

Common Tree Algorithms

Trees have a variety of algorithms for traversal and manipulation. The most common are traversal algorithms, which visit each node in the tree exactly once.

Tree Traversal

There are two main approaches to traversing a tree:

Depth-First Search (DFS): This approach explores as far as possible down one branch before backtracking. There are three common ways to perform DFS:
- In-order Traversal: Visit the left subtree, then the root, then the right subtree. For a BST, this traversal visits the nodes in ascending order.
- Pre-order Traversal: Visit the root, then the left subtree, then the right subtree. This is useful for creating a copy of the tree.
- Post-order Traversal: Visit the left subtree, then the right subtree, then the root. This is useful for deleting nodes from the tree.
Breadth-First Search (BFS): This approach explores the tree level by level. It visits all the nodes at a given depth before moving on to the next level. BFS is typically implemented using a queue.

More Tree Algorithms in Go

Let's explore how to implement some of these fundamental tree algorithms in Go.

Finding the Height/Depth of a Binary Tree

The height of a binary tree is the number of edges on the longest path from the root node to a leaf node. A tree with only a root node has a height of 0.

The concept is closely related to the depth of a node, which is its distance from the root. The height of the tree is, therefore, the maximum depth of any node in the tree.

We can calculate the height recursively. The height of a node is 1 plus the maximum height of its left or right subtree.

DATA_NODE: go

import "math" // TreeNode definition from before type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func max(a, b int) int { if a > b { return a } return b } func height(node *TreeNode) int { if node == nil { return -1 // Height of a null tree is -1 } leftHeight := height(node.Left) rightHeight := height(node.Right) return 1 + max(leftHeight, rightHeight) }

DFS Traversals in Go

Here are the Go implementations for the three DFS traversal methods.

In-order Traversal

DATA_NODE: go

func inOrderTraversal(node *TreeNode) { if node == nil { return } inOrderTraversal(node.Left) fmt.Println(node.Val) // Process the node inOrderTraversal(node.Right) }

Pre-order Traversal

DATA_NODE: go

func preOrderTraversal(node *TreeNode) { if node == nil { return } fmt.Println(node.Val) // Process the node preOrderTraversal(node.Left) preOrderTraversal(node.Right) }

Post-order Traversal

DATA_NODE: go

func postOrderTraversal(node *TreeNode) { if node == nil { return } postOrderTraversal(node.Left) postOrderTraversal(node.Right) fmt.Println(node.Val) // Process the node }

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

Now, let's apply our knowledge to a classic problem.

The Lowest Common Ancestor (LCA) of two nodes, p and q, in a tree is the lowest (i.e., deepest) node that has both p and q as descendants.

The Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

For example, consider the following BST:

6 / \ 2 8 / \ / \ 0 4 7 9 / \ 3 5

The LCA of nodes 2 and 8 is 6.
The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself.
The LCA of nodes 3 and 5 is 4.

The Solution

The properties of a BST make finding the LCA particularly efficient.

We can start at the root of the tree and use the values of p and q to decide where to go next.

Let's consider the current node we are at, let's call it current.

If both p and q are greater than current.val, it means that the LCA must be in the right subtree. So, we move to the right child.
If both p and q are less than current.val, it means that the LCA must be in the left subtree. So, we move to the left child.
If one of p or q is greater than current.val and the other is less than current.val (or if one of them is equal to current.val), then current is the LCA.

This is because p and q are on opposite sides of the current node, meaning it's the split point and thus the lowest common ancestor.

We can implement this logic both iteratively and recursively.

Iterative Solution

DATA_NODE: go

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { current := root for current != nil { if p.Val > current.Val && q.Val > current.Val { current = current.Right } else if p.Val < current.Val && q.Val < current.Val { current = current.Left } else { return current } } return nil // Should not be reached in a valid BST }

Recursive Solution

DATA_NODE: go

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil { return nil } if p.Val > root.Val && q.Val > root.Val { return lowestCommonAncestor(root.Right, p, q) } else if p.Val < root.Val && q.Val < root.Val { return lowestCommonAncestor(root.Left, p, q) } else { return root } }

Both of these solutions are very efficient, with a time complexity of O(H), where H is the height of the tree. In a balanced BST, this is O(log N), where N is the number of nodes.

The space complexity for the iterative solution is O(1), while the recursive solution has a space complexity of O(H) due to the call stack.

Alternative: Stack-Based Solution

Another way to solve this problem is by finding the path from the root to each of the two nodes, p and q. Once we have both paths, we can compare them to find the last common node, which is the LCA.

This method is more generic and would also work for a regular binary tree, but it's less efficient for a BST than the previous solutions because it requires traversing parts of the tree multiple times and uses extra space to store the paths.

Here is the implementation in Go:

DATA_NODE: go

// Helper function to find the path from the root to a target node func getPath(root, target *TreeNode) []*TreeNode { path := []*TreeNode{} current := root for current != nil { path = append(path, current) if target.Val < current.Val { current = current.Left } else if target.Val > current.Val { current = current.Right } else { break // Found the target } } return path } func lowestCommonAncestorWithStacks(root, p, q *TreeNode) *TreeNode { pathP := getPath(root, p) pathQ := getPath(root, q) var lca *TreeNode // Iterate through both paths until they diverge for i := 0; i < len(pathP) && i < len(pathQ); i++ { if pathP[i] == pathQ[i] { lca = pathP[i] } else { break } } return lca }

Conclusion

Trees and Binary Search Trees are powerful data structures that are essential for any programmer's toolkit. By understanding their properties and the algorithms that operate on them, you can solve a wide range of problems efficiently.

The Lowest Common Ancestor problem is a perfect example of how the structure of a BST can be leveraged to find an elegant and optimal solution.

Lowest Common Ancestor with Binary Search Tree

Understanding Trees, Binary Search Trees, and Finding the Lowest Common Ancestor

What is a Tree?

Key Terminology:

Binary Search Trees (BSTs)

Common Tree Algorithms

Tree Traversal

More Tree Algorithms in Go

Finding the Height/Depth of a Binary Tree

DFS Traversals in Go

In-order Traversal

Pre-order Traversal

Post-order Traversal

LeetCode 235: Lowest Common Ancestor of a Binary Search Tree

The Problem

The Solution

Iterative Solution

Recursive Solution

Alternative: Stack-Based Solution

Conclusion

// INTEL_SPECIFICATIONS

// SERIES_DATA