ProgramGuru

Find the kth Largest Element in a Binary Search Tree

Problem and examples

You are given a Binary Search Tree (BST) and an integer k. Your task is to find the kth largest element in the BST. In a BST, the left subtree of a node contains nodes with values less than the node’s value, and the right subtree contains nodes with values greater than the node’s value.

The tree will contain unique values, and k is guaranteed to be a positive integer no greater than the number of nodes in the tree.

Input Tree (Level Order) k Kth Largest Description
[5, 3, 7, 2, 4, 6, 8] 3 6 In descending order [8, 7, 6, 5, 4, 3, 2], the 3rd largest is 6.
[20, 10, 30, 5, 15, 25, 35] 1 35 Largest element in the BST is 35 (rightmost leaf).
[15, 10, 20, null, 12, 17, 25] 5 12 Descending order is [25, 20, 17, 15, 12, 10]; 5th largest is 12.
[50, 30, 70, 20, 40, 60, 80] 7 20 In descending order [80, 70, 60, 50, 40, 30, 20]; 7th largest is 20.
[10] 1 10 Single node is both the largest and smallest, so 1st largest is 10.
[] 1 null Empty tree has no nodes, so kth largest is undefined (null).

Explore Find the kth Largest Element in a Binary Search Tree

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a Binary Search Tree (BST), and we need to find the kth largest element in it. A BST has the property that for any given node, the left subtree contains values less than the node, and the right subtree contains values greater than the node.

To solve this, we can utilize reverse in-order traversal (right → node → left), which visits nodes in descending order. This approach allows us to find the kth largest element efficiently by counting how many nodes we’ve visited so far during the traversal.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s consider the example BST: [5,3,6,2,4,null,null,1].

This represents the following BST structure:


        5
       /       3   6
     /     2   4
   /
  1

We are asked to find the k = 3rd largest element.

Step 2: Understand Reverse In-Order Traversal

In normal in-order traversal (Left → Node → Right), we get sorted ascending order. But here, we use reverse in-order (Right → Node → Left) to get descending order. As we visit each node, we keep a count.

Step 3: Traverse and Count

Start from the rightmost node (which is the largest):

  1. Visit 6 → count = 1
  2. Backtrack to 5 → count = 2
  3. Go to left child 3, then right child 4 → count = 3

Since count = 3 at node 4, we return 4 as the answer.

Step 4: Code Outline

We define a helper function to do reverse in-order traversal recursively, while maintaining a counter and storing the result once we reach the kth element.


// Java-style pseudocode
int count = 0;
int result = -1;

void reverseInorder(TreeNode node, int k) {
    if (node == null || count >= k) return;
    reverseInorder(node.right, k);
    count++;
    if (count == k) {
        result = node.val;
        return;
    }
    reverseInorder(node.left, k);
}

Edge Cases

Case 1: k = 1 (Largest Element)

When k = 1, we want the largest element. Since the rightmost node in a BST is the largest, we can directly return the value of the rightmost node if we reach it first during traversal.

Case 2: Small BST

For a small BST like [2,1,3], reverse traversal visits nodes in the order [3,2,1]. If k = 2, the answer is 2.

Case 3: Single Node Tree

If the tree has just one node, say [5], then the only valid k is 1. The 1st largest element is the node itself: 5.

Case 4: Empty Tree

If the tree is empty, there are no elements to return. Any k in this scenario is invalid, and we must return an error or handle it gracefully (e.g., return -1 or throw an exception).

Case 5: k Greater Than Number of Nodes

If k is larger than the total number of nodes, the traversal will finish without finding the kth largest. We should check node count beforehand or handle this as an invalid input.

Finally

This problem teaches us how to apply a traversal technique that respects the properties of BSTs to solve problems efficiently. By understanding reverse in-order traversal and maintaining a count, we can find the kth largest element in O(H + k) time, where H is the height of the tree. Always remember to consider edge cases like empty trees, invalid k values, and small tree structures during implementation.

  1. Given a binary search tree (BST) and an integer k.
  2. Perform a reverse in-order traversal (visit right subtree, then node, then left subtree) to process nodes in descending order.
  3. Maintain a counter of visited nodes.
  4. When the counter equals k, record the current node's value as the kth largest element and terminate the traversal.
  5. Return the recorded value.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

void reverseInorder(TreeNode* root, int k, int* count, int* result) {
    if (!root) return;
    reverseInorder(root->right, k, count, result);
    (*count)++;
    if (*count == k) {
        *result = root->val;
        return;
    }
    reverseInorder(root->left, k, count, result);
}

int kthLargest(TreeNode* root, int k) {
    int count = 0, result = -1;
    reverseInorder(root, k, &count, &result);
    return result;
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right = createNode(7);
    root->right->right = createNode(8);
    int k = 2;
    printf("%d\n", kthLargest(root, k));
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};

void reverseInorder(TreeNode* root, int k, int& count, int& result) {
    if (!root) return;
    reverseInorder(root->right, k, count, result);
    count++;
    if (count == k) {
        result = root->val;
        return;
    }
    reverseInorder(root->left, k, count, result);
}

int kthLargest(TreeNode* root, int k) {
    int count = 0, result = -1;
    reverseInorder(root, k, count, result);
    return result;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right = new TreeNode(7);
    root->right->right = new TreeNode(8);
    int k = 2;
    cout << kthLargest(root, k) << endl;
    return 0;
}

Python implementation

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

def kthLargest(root, k):
    count = 0
    result = None

    def traverse(node):
        nonlocal count, result
        if not node or result is not None:
            return
        traverse(node.right)
        count += 1
        if count == k:
            result = node.val
            return
        traverse(node.left)

    traverse(root)
    return result

# Example usage
if __name__ == '__main__':
    root = TreeNode(5,
        TreeNode(3, TreeNode(2), TreeNode(4)),
        TreeNode(7, None, TreeNode(8))
    )
    k = 2
    print(kthLargest(root, k))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class KthLargestBST {
    public int kthLargest(TreeNode root, int k) {
        int[] count = new int[1];
        int[] result = new int[1];
        reverseInorder(root, k, count, result);
        return result[0];
    }

    private void reverseInorder(TreeNode node, int k, int[] count, int[] result) {
        if (node == null) return;
        reverseInorder(node.right, k, count, result);
        count[0]++;
        if (count[0] == k) {
            result[0] = node.val;
            return;
        }
        reverseInorder(node.left, k, count, result);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,
            new TreeNode(3, new TreeNode(2), new TreeNode(4)),
            new TreeNode(7, null, new TreeNode(8))
        );
        int k = 2;
        System.out.println(new KthLargestBST().kthLargest(root, k));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthLargest(root, k) {
    let count = 0;
    let result = null;

    function traverse(node) {
        if (!node || result !== null) return;
        traverse(node.right);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        traverse(node.left);
    }

    traverse(root);
    return result;
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, null, new TreeNode(8))
);
const k = 2;
console.log(kthLargest(root, k));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func kthLargest(root *TreeNode, k int) int {
    var result int
    var count int
    var reverseInorder func(*TreeNode)

    reverseInorder = func(node *TreeNode) {
        if node == nil || count >= k {
            return
        }
        reverseInorder(node.right)
        count++
        if count == k {
            result = node.val
            return
        }
        reverseInorder(node.left)
    }

    reverseInorder(root)
    return result
}

func main() {
    root := &TreeNode{5,
        &TreeNode{3, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}},
        &TreeNode{7, nil, &TreeNode{8, nil, nil}},
    }
    k := 2
    fmt.Println(kthLargest(root, k))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn kth_largest(root: &Option<Box<TreeNode>>, k: i32) -> i32 {
    fn traverse(node: &Option<Box<TreeNode>>, k: i32, count: &mut i32, result: &mut i32) {
        if let Some(n) = node {
            traverse(&n.right, k, count, result);
            *count += 1;
            if *count == k {
                *result = n.val;
                return;
            }
            traverse(&n.left, k, count, result);
        }
    }
    let mut count = 0;
    let mut result = -1;
    traverse(root, k, &mut count, &mut result);
    result
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 5,
        left: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode::new(2))),
            right: Some(Box::new(TreeNode::new(4))),
        })),
        right: Some(Box::new(TreeNode {
            val: 7,
            left: None,
            right: Some(Box::new(TreeNode::new(8))),
        })),
    }));
    let k = 2;
    println!("{}", kth_largest(&root, k));
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun kthLargest(root: TreeNode?, k: Int): Int {
    var count = 0
    var result = -1

    fun traverse(node: TreeNode?) {
        if (node == null || count >= k) return
        traverse(node.right)
        count++
        if (count == k) {
            result = node.value
            return
        }
        traverse(node.left)
    }

    traverse(root)
    return result
}

fun main() {
    val root = TreeNode(5).apply {
        left = TreeNode(3).apply {
            left = TreeNode(2)
            right = TreeNode(4)
        }
        right = TreeNode(7).apply {
            right = TreeNode(8)
        }
    }
    val k = 2
    println(kthLargest(root, k))
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func kthLargest(_ root: TreeNode?, _ k: Int) -> Int {
    var count = 0
    var result = -1

    func traverse(_ node: TreeNode?) {
        guard let node = node, count < k else { return }
        traverse(node.right)
        count += 1
        if count == k {
            result = node.val
            return
        }
        traverse(node.left)
    }

    traverse(root)
    return result
}

let root = TreeNode(5)
root.left = TreeNode(3)
root.left?.left = TreeNode(2)
root.left?.right = TreeNode(4)
root.right = TreeNode(7)
root.right?.right = TreeNode(8)
let k = 2
print(kthLargest(root, k))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function kthLargest(root: TreeNode | null, k: number): number {
    let count = 0;
    let result: number = -1;

    function traverse(node: TreeNode | null) {
        if (!node || result !== -1) return;
        traverse(node.right);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        traverse(node.left);
    }

    traverse(root);
    return result;
}

const root = new TreeNode(5,
    new TreeNode(3, new TreeNode(2), new TreeNode(4)),
    new TreeNode(7, null, new TreeNode(8))
);
const k = 2;
console.log(kthLargest(root, k));