Freedom Day Special: 85% OFF on .NET AI & Architect Career
Ends in
00d
00h
00m
00s
 Get Now
Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Kth Largest Element in BST

Medium Acceptance 70.53% Points 30.00

You are given the root of a Binary Search Tree (BST) and an integer k. Your task is to find the kth largest value among all node values in the tree.

Return the kth largest element present in the BST.

Examples
Example 1

image Input: root = [5,3,8,1,4,null,9], k = 2
Output: 8
Explanation: In descending order the values are 9, 8, 5, 4, 3, 1. The 2nd largest value is 8.

Example 2

image Input: root = [5,3,8,1,4,null,9], k = 1
Output: 9
Explanation: The largest value in the BST is 9.

Example 3

image Input: root = [42], k = 1
Output: 42
Explanation: The only value is both the largest and the 1st largest element.

Hints
Hint 1
In a BST:
Hint 2
  • An inorder traversal visits nodes in ascending order.
Hint 3
  • A reverse inorder traversal (Right ? Root ? Left) visits nodes in descending order.
Constraints
    • 1 = Number of nodes = 104
    • 1 = k = Number of nodes
    • -10? = Node.data = 10?
Companies
Flipkart Sprinklr
Topics
Tree Traversal Binary Tree
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions