Kth Node in a Binary Search Tree

1. Problem Description

Given a binary search tree, find its kth smallest node. For example, in (5, 3, 7, 2, 4, 6, 8), the value of the third smallest node is 4.

2. Approach

• Inorder traversal

3. Code

3.1. Inorder Traversal

• java

public class 二叉搜索树的第k个结点
{
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        // Check whether the parameters are valid
        if (pRoot == null || k <= 0)
        {
            return null;
        }
        // Generate an ordered list through inorder traversal
        List<TreeNode> list = new LinkedList<>();
        this.midOrder(list, pRoot);
        // Take the kth node
        if (list.size() < k)
        {
            return null;
        }
        return list.get(k-1);
    }


    private void midOrder(List<TreeNode> list, TreeNode pRoot)
    {
        if (pRoot.left != null)
        {
            this.midOrder(list, pRoot.left);
        }

        list.add(pRoot);

        if (pRoot.right != null)
        {
            this.midOrder(list, pRoot.right);
        }
    }
}

• go

// Time: O(N)
// Space: O(N)
func KthNode(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil || k <= 0 {
		return nil
	}

	orders := make([]*TreeNode, 0)
	midOrderKthNode(pRoot, &orders)
	if len(orders) < k {
		return nil

	}
	return orders[k-1]
}

func midOrderKthNode(root *TreeNode, nodes *[]*TreeNode) {
	if root == nil {
		return
	}

	midOrderKthNode(root.Left, nodes)
	*nodes = append(*nodes, root)
	midOrderKthNode(root.Right, nodes)

}



// Time: O(N)
// Space: O(h)
func KthNode2(pRoot *TreeNode, k int) *TreeNode {
	if pRoot == nil || k <= 0 {
		return nil
	}

	current := 0
	return kthNode(pRoot, &current, k)
}

func kthNode(n *TreeNode, current *int, k int) *TreeNode {
	if n == nil {
		return nil
	}
	if node := kthNode(n.Left, current, k); node != nil {
		return node
	}
	*current = *current + 1
	if *current == k {
		return n
	}
	if node := kthNode(n.Right, current, k); node != nil {
		return node
	}
	return nil
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargest(root *TreeNode, k int) int {
    if root == nil || k <= 0 { return 0 }
    count := 0
    if node := kthLargestDFS(root, k, &count); node != nil {
        return node.Val
    }
    return 0
}

func kthLargestDFS(root *TreeNode, k int, count *int) *TreeNode {
    if root == nil || k <= 0 {return nil}
    if node := kthLargestDFS(root.Right, k, count); node != nil {
        return node
    }
    (*count)++
    if *count == k {
        return root
    }
    if node := kthLargestDFS(root.Left, k, count); node != nil {
        return node
    }
    return nil
}

4. References

• K-th Node in a Binary Search Tree - NowCoder
• Sword Offer 54. K-th Largest Node in a Binary Search Tree - LeetCode
• Kth Smallest Element in a BST - LeetCode