...
/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.
We'll cover the following...
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 traversalstatic 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 ...