...

/

Solution Review: Finding Kth Maximum Value in Binary Search Tree

Solution Review: Finding Kth Maximum Value in Binary Search Tree

A detailed analysis of the different ways to solve the “Finding Kth Maximum Value in Binary Search Tree” challenge.

Solution 1: Sorting the tree in order #

Press + to interact
main.cs
BST.cs
ArrayList.cs
using System;
namespace chapter_6
{
class Solution
{
//Helper recursive function to traverse tree using inorder traversal
static void inOrderTraversal(Node rootNode, ArrayList result)
{
if (rootNode != null)
{
inOrderTraversal(rootNode.leftChild, result);
result.insert(rootNode.value);
inOrderTraversal(rootNode.rightChild, result);
}
}
static int findKthMax(Node rootNode, int k, int nodes)
{
if (k <= 0)
{
return -1;
}
//Perform In-Order Traversal to get sorted array. (ascending order)
//Return value at index [length - k]
ArrayList result = new ArrayList(nodes);
inOrderTraversal(rootNode, result);
return result.getAt(nodes - k);
}
static void Main(string[] args)
{
BinarySearchTree bsT = new BinarySearchTree(6);
bsT.insertBST(4);
bsT.insertBST(9);
bsT.insertBST(5);
bsT.insertBST(2);
bsT.insertBST(8);
Console.WriteLine(findKthMax(bsT.getRoot(), 3, 6));
return;
}
}
}

In this solution, sort the tree in order by using a variation of the inOrderPrint() function that was studied in the “In-Order Traversal” lesson, and return the kk ...