• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The KTH largest node in the binary search tree

Given a binary search tree, find the KTH largest node.

Example 1: Input: root = [3,1,4, NULL,2], k = 1 3 / \ 1 4\2 Output: 4 Example 2: Input: Root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4/1 output: 4Copy the code

Source: LeetCode link: leetcode-cn.com/problems/er…

• The first way
  • Keep pushing the nodes in the right subtree
  • When the right subtree is empty, the elastic stack traverses the left subtree as the current node
  • The counter increments by 1 and returns when the counter is equal to k

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        int count = 1;    // The root node itself counts as 1
        while(Objects.nonNull(root) || ! stack.empty()){while(Objects.nonNull(root)){
                stack.push(root);   // if it is not empty, it is pushed
                root = root.right;   // The right subtree is larger than the root, so the next step goes directly to the right subtree
            }
            TreeNode pop = stack.pop();
            if(count == k){
                return pop.val;  // The KTH large node has been found
            }
            count++;
            root = pop.left;   // After traversing the right node, we come to the left subtree of the child root node
        }
        return 0; }}Copy the code

• The second approach is a little more intuitive
  • Use the properties of binary search trees
  • The middle order traversal of a binary search tree is the output from large to small
  • So every time I walk through an element,kDo the subtraction operation

class Solution { int res, k; public int kthLargest(TreeNode root, int k) { this.k = k; dfs(root); return res; } void dfs(TreeNode root) { if(root == null) return; dfs(root.right); if(k == 0) return; if(--k == 0) res = root.val; dfs(root.left); }}Copy the code