Find the kth largest node in a binary search tree

You're midway through a Twitter phone screen when the interviewer asks, "Given a binary search tree, how would you find the 3rd largest element?" It sounds straightforward at first, but then you realize it requires connecting two ideas: the BST ordering property and in-order traversal. This problem, also known as "Kth Largest Element in a BST" on other platforms, is a favorite at companies like Twitter and Facebook because it tests whether you truly understand how BSTs organize data.

TL;DR

Perform an in-order traversal of the BST to collect all node values into a sorted list. Since in-order traversal visits BST nodes in ascending order, the kth largest element sits at index size - k in that list. This runs in O(n) time and O(n) space. The key insight is that you don't need to sort anything yourself; the BST structure combined with in-order traversal gives you sorted order for free.

Why This Problem Matters

Finding the kth largest element in a BST bridges two fundamental concepts: tree traversal and the BST ordering property. Interviewers love it because it reveals whether a candidate can leverage data structure properties to simplify a problem. If you understand why in-order traversal produces sorted output from a BST, you can solve this in a few lines of code. If you don't, you'll find yourself reaching for unnecessary sorting algorithms.

BST Refresher: The Ordering Property

A binary search tree enforces a simple but powerful rule: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

This property holds recursively at every node in the tree, not just the root. It's what makes BSTs useful for search operations and, critically for our problem, it's what makes in-order traversal produce sorted output.

Here's a fuller example with seven nodes:

Notice how 2 and 4 are both in the left subtree of 5 (both smaller), while 7 and 10 are in the right subtree (both larger). This ordering extends all the way down.

Understanding the Problem

Let's break down what we're asked to do:

Given: The root of a BST and an integer k Find: The data value of the kth largest node Constraints: The tree has at least k nodes and at most 1000 nodes

Here's the example from the problem:

For this tree, kthLargest(root, 4) returns 4. The in-order traversal gives us [2, 4, 5, 8, 10]. Counting from the largest: 10 is 1st, 8 is 2nd, 5 is 3rd, 4 is 4th. So the 4th largest is 4.

Edge Cases Worth Considering

1. k = 1: Return the maximum node (rightmost in the BST)
2. k = n (total nodes): Return the minimum node (leftmost in the BST)
3. Single node tree: Only valid for k = 1, return that node's value
4. Skewed tree (all nodes on one side): The algorithm still works because in-order traversal handles any BST shape

The Key Insight: In-Order Traversal

In-order traversal visits nodes in the order: left subtree, current node, right subtree. For a BST, this produces all values in ascending sorted order. No sorting step needed.

For the tree above, in-order traversal visits: 2, 3, 4, 5, 7, 8, 10. That's already sorted. To find the kth largest, we just grab the element at index size - k from this sorted list.

Why size - k? If we have 7 elements sorted in ascending order and want the 3rd largest, that's the element at position 7 - 3 = 4 (0-indexed), which is 7. The 1st largest is at index 6 (which is 10), the 2nd at index 5 (which is 8), and so on.

Let's watch the in-order traversal in action on our problem example:

After the traversal completes, we have [2, 4, 5, 8, 10]. For k = 4, we access index 5 - 4 = 1, which gives us 4.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.LinkedList;
import java.util.List;

public class Solution {
  public int kthLargest(TreeNode root, int k) {
    // Collect all node values via in-order traversal
    List<Integer> dataValues = new LinkedList<>();
    buildInOrder(root, dataValues);

    // The kth largest is at index (size - k) in the sorted list
    return dataValues.get(dataValues.size() - k);
  }

  private void buildInOrder(TreeNode node, List<Integer> dataValues) {
    if (node != null) {
      buildInOrder(node.left, dataValues);
      dataValues.add(node.data);
      buildInOrder(node.right, dataValues);
    }
  }
}

The solution has two parts. The buildInOrder method performs a standard in-order traversal, appending each node's value to the list as it visits the node. The kthLargest method calls this helper, then indexes into the resulting sorted list.

Let's trace through kthLargest(root, 3) on the tree [5, 4, 8, 2, #, #, 10]:

1. buildInOrder visits: 2, 4, 5, 8, 10
2. dataValues = [2, 4, 5, 8, 10]
3. dataValues.size() - k = 5 - 3 = 2
4. dataValues.get(2) = 5

The 3rd largest element is 5. This checks out: 10 (1st), 8 (2nd), 5 (3rd).

Complexity Analysis

Time Complexity: O(n)

We visit every node exactly once during the in-order traversal. Each visit does constant work (one list append and two recursive calls). The final index lookup is O(1). So the total time is O(n), where n is the number of nodes.

Space Complexity: O(n)

We store all n node values in the list, which takes O(n) space. The recursion call stack adds O(h) space where h is the tree height (O(log n) for a balanced tree, O(n) for a skewed tree), but the list dominates.

Can We Do Better?

Yes. Instead of collecting all values, we could perform a reverse in-order traversal (right, root, left), which visits nodes in descending order. We maintain a counter and stop as soon as we hit the kth node. This runs in O(h + k) time and O(h) space, which is significantly better when k is small relative to n. However, the list-based approach is simpler to implement and perfectly acceptable in an interview setting.

Common Pitfalls

1. Forgetting the BST property: Some candidates sort the collected values, not realizing in-order traversal already gives sorted output. This wastes an O(n log n) sort step.

2. Off-by-one on the index: The kth largest in a list of size n is at index n - k, not n - k + 1 or n - k - 1. Double-check with a small example: in [1, 2, 3], the 1st largest (3) is at index 3 - 1 = 2.

3. Confusing kth largest with kth smallest: The kth smallest is at index k - 1. The kth largest is at index size - k. Mixing these up is an easy mistake under interview pressure.

4. Using a regular binary tree traversal: In-order traversal only produces sorted output on a BST. On a regular binary tree, the values come out in no particular order.

Interview Tips

When you encounter this problem:

1. State the BST property explicitly: "In a BST, in-order traversal produces sorted output." This immediately signals to the interviewer that you understand the core insight.

2. Discuss the trade-off: After presenting the O(n) solution, mention the reverse in-order approach as an optimization. Interviewers appreciate candidates who can identify improvements even if they implement the simpler version.

3. Walk through an example: Pick a small tree (5-7 nodes), write out the in-order result, and show how indexing with size - k gives the correct answer.

4. Consider follow-ups: The interviewer might ask about kth smallest (index k - 1), or how to handle repeated queries efficiently (augmented BST with subtree sizes).

Key Takeaways

• In-order traversal of a BST produces node values in ascending sorted order. This is the fundamental property that makes the solution simple.
• The kth largest element in a sorted list of size n is at index n - k. No sorting step is needed because the BST structure gives us sorted order for free.
• The O(n) list-based approach is clean and interview-safe. For production code with repeated queries, consider augmenting the BST with subtree sizes for O(h) lookups.
• Reverse in-order traversal (right, root, left) visits nodes in descending order and can find the kth largest in O(h + k) time by stopping early.
• This problem bridges tree traversal and BST properties. If you understand both concepts individually, combining them here is straightforward.

Solutions in Other Languages

Python

class Solution:
    def kth_largest(self, root, k):
        data_values = []
        self.build_in_order(root, data_values)
        return data_values[len(data_values) - k]

    def build_in_order(self, node, data_values):
        if node is not None:
            self.build_in_order(node.left, data_values)
            data_values.append(node.data)
            self.build_in_order(node.right, data_values)

JavaScript

class Solution {
  kthLargest(root, k) {
    const dataValues = [];
    this.buildInOrder(root, dataValues);
    return dataValues[dataValues.length - k];
  }

  buildInOrder(node, dataValues) {
    if (node !== null) {
      this.buildInOrder(node.left, dataValues);
      dataValues.push(node.data);
      this.buildInOrder(node.right, dataValues);
    }
  }
}

TypeScript

class Solution {
  kthLargest(root: TreeNode | null, k: number): number {
    const dataValues: number[] = [];
    this.buildInOrder(root, dataValues);
    return dataValues[dataValues.length - k];
  }

  buildInOrder(node: TreeNode | null, dataValues: number[]): void {
    if (node !== null) {
      this.buildInOrder(node.left, dataValues);
      dataValues.push(node.data);
      this.buildInOrder(node.right, dataValues);
    }
  }
}

C++

#include <vector>

class Solution {
public:
  int kthLargest(TreeNode *root, int k) {
    std::vector<int> dataValues;
    buildInOrder(root, dataValues);
    return dataValues[dataValues.size() - k];
  }

private:
  void buildInOrder(TreeNode *node, std::vector<int> &dataValues) {
    if (node != nullptr) {
      buildInOrder(node->left, dataValues);
      dataValues.push_back(node->data);
      buildInOrder(node->right, dataValues);
    }
  }
};

Scala

import scala.collection.mutable

class Solution {
  def kthLargest(root: TreeNode, k: Int): Int = {
    val dataValues = mutable.ArrayBuffer[Int]()
    buildInOrder(root, dataValues)
    dataValues(dataValues.length - k)
  }

  private def buildInOrder(
    node: TreeNode,
    dataValues: mutable.ArrayBuffer[Int]
  ): Unit = {
    if (node != null) {
      buildInOrder(node.left, dataValues)
      dataValues.append(node.data)
      buildInOrder(node.right, dataValues)
    }
  }
}

Kotlin

class Solution {
    fun kthLargest(root: TreeNode?, k: Int): Int {
        val dataValues = mutableListOf<Int>()
        buildInOrder(root, dataValues)
        return dataValues[dataValues.size - k]
    }

    private fun buildInOrder(node: TreeNode?, dataValues: MutableList<Int>) {
        if (node != null) {
            buildInOrder(node.left, dataValues)
            dataValues.add(node.data)
            buildInOrder(node.right, dataValues)
        }
    }
}

Swift

class Solution {
    func kthLargest(_ root: TreeNode?, _ k: Int) -> Int {
        var dataValues = [Int]()
        buildInOrder(root, &dataValues)
        return dataValues[dataValues.count - k]
    }

    private func buildInOrder(_ node: TreeNode?, _ dataValues: inout [Int]) {
        if let node = node {
            buildInOrder(node.left, &dataValues)
            dataValues.append(node.data)
            buildInOrder(node.right, &dataValues)
        }
    }
}

Ruby

class Solution
  def kth_largest(root, k)
    data_values = []
    build_in_order(root, data_values)
    data_values[data_values.size - k]
  end

  def build_in_order(node, data_values)
    if node
      build_in_order(node.left, data_values)
      data_values << node.data
      build_in_order(node.right, data_values)
    end
  end
end

Rust

impl Solution {
    pub fn kth_largest(&self, root: Option<Box<TreeNode>>, k: i32) -> i32 {
        let mut data_values: Vec<i32> = Vec::new();
        Self::build_in_order(&root, &mut data_values);
        data_values[data_values.len() - k as usize]
    }

    fn build_in_order(node: &Option<Box<TreeNode>>, data_values: &mut Vec<i32>) {
        if let Some(current) = node {
            Self::build_in_order(&current.left, data_values);
            data_values.push(current.data);
            Self::build_in_order(&current.right, data_values);
        }
    }
}

C#

public class Solution {
    public int kthLargest(TreeNode? root, int k) {
        var dataValues = new List<int>();
        BuildInOrder(root, dataValues);
        return dataValues[dataValues.Count - k];
    }

    private void BuildInOrder(TreeNode? node, List<int> dataValues) {
        if (node != null) {
            BuildInOrder(node.left, dataValues);
            dataValues.Add(node.data);
            BuildInOrder(node.right, dataValues);
        }
    }
}

Dart

class Solution {
  int kthLargest(TreeNode? root, int k) {
    List<int> dataValues = [];
    buildInOrder(root, dataValues);
    return dataValues[dataValues.length - k];
  }

  void buildInOrder(TreeNode? node, List<int> dataValues) {
    if (node != null) {
      buildInOrder(node.left, dataValues);
      dataValues.add(node.data);
      buildInOrder(node.right, dataValues);
    }
  }
}

PHP

class Solution {
    public function kthLargest(?TreeNode $root, int $k): int {
        $dataValues = [];
        $this->buildInOrder($root, $dataValues);
        return $dataValues[count($dataValues) - $k];
    }

    private function buildInOrder(?TreeNode $node, array &$dataValues): void {
        if ($node !== null) {
            $this->buildInOrder($node->left, $dataValues);
            $dataValues[] = $node->data;
            $this->buildInOrder($node->right, $dataValues);
        }
    }
}

Related Problems

Once you're comfortable with this problem, try these to deepen your BST traversal skills:

• Find the kth smallest node in a BST (the mirror of this problem)
• Validate a binary search tree
• Find the lowest common ancestor in a BST
• Convert a sorted array to a balanced BST

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or targeting your next role at a company like Twitter or Facebook, mastering BST fundamentals like this will serve you well.