Cookie Consent by Free Privacy Policy Generator 📌 LeetCode Meditations: Kth Smallest Element in a BST


✅ LeetCode Meditations: Kth Smallest Element in a BST


💡 Newskategorie: Programmierung
🔗 Quelle: dev.to

Let's start with the description for Kth Smallest Element in a BST:

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

For example:

Example image 1

Input: root = [3, 1, 4, null, 2], k = 1
Output: 1

Or:

Example image 2

Input: root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: 3

This problem naturally lends itself to a neat recursive solution using a neat traversal algorithm.

Remember inorder traversal that gives us the values in a binary search tree in order? Exactly.

Here, we can use it to build a stack called values, and get the kth item (1-indexed of course, as the problem description states):

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function kthSmallest(root: TreeNode | null, k: number): number {
  let values = [];
  function inorderWalk(node: TreeNode | null) {
    if (node === null || values.length === k) {
      return;
    }

    inorderWalk(node.left);
    values.push(node.val);
    inorderWalk(node.right);
  }

  inorderWalk(root);

  return values[k - 1];
}

Time and space complexity

The time complexity is going to be O(n)O(n) O(n) because we traverse the whole tree and visit each node once. The space complexity is also O(n)O(n) O(n) as we keep a stack that holds all the nodes.

That was a simple and elegant solution, but let's now take a breath and look at another solution that uses an iterative version of the inorder traversal:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function kthSmallest(root: TreeNode | null, k: number): number {
  let stack = [];
  let currentNode = root;

  while (k > 0) {
    while (currentNode !== null) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    }

    currentNode = stack.pop();
    k--;

    if (k === 0) {
      return currentNode.val;
    }

    currentNode = currentNode.right;
  }
}

Here, we go as deep as we can in the left subtree, adding the nodes to our stack as we go. Once we reach a node that doesn't have a left child, we pop from the stack. Each time we do so, we'll be getting the values in sorted order.
Once we pop the kth time, we'll return the value of the current node and be done with it. Otherwise, we'll go to the right subtree.

Time and space complexity

The time complexity is O(n)O(n) O(n) because in the worst case where k is nn n , we'll end up visiting each node. The space complexity will be O(h)O(h) O(h) —where hh h is the height of the tree—because in the worst case, we'll store all the nodes from the root to the deepest leaf node.

The next problem is called Construct Binary Tree from Preorder and Inorder Traversal. Yet another mouthful title, but we'll survive. Until then, happy coding.

...

✅ LeetCode Meditations: Kth Smallest Element in a BST


📈 121.2 Punkte

✅ Count distinct element in a BST


📈 39.32 Punkte

✅ Find the Kth occurrence of an element in a sorted Array


📈 39.32 Punkte

✅ Minimum cost to make every Kth element in Array equal


📈 39.32 Punkte

✅ LeetCode Meditations: Merge K Sorted Lists


📈 35.83 Punkte

✅ LeetCode Meditations — Chapter 11: Graphs


📈 35.83 Punkte

✅ LeetCode Meditations: Binary Tree Maximum Path Sum


📈 35.83 Punkte

✅ LeetCode Meditations: Reorder List


📈 35.83 Punkte

✅ LeetCode Meditations: Word Search II


📈 35.83 Punkte

✅ LeetCode Meditations: Construct Binary Tree from Preorder and Inorder Traversal


📈 35.83 Punkte

✅ LeetCode Meditations: Longest Palindromic Substring


📈 35.83 Punkte

✅ LeetCode Meditations: Reverse Linked List


📈 35.83 Punkte

✅ LeetCode Meditations: Design Add and Search Words Data Structure


📈 35.83 Punkte

✅ LeetCode Meditations: Validate Binary Search Tree


📈 35.83 Punkte

✅ LeetCode Meditations: House Robber II


📈 35.83 Punkte

✅ LeetCode Meditations: Two Sum


📈 35.83 Punkte

✅ LeetCode Meditations: Implement Trie (Prefix Tree)


📈 35.83 Punkte

✅ LeetCode Meditations: Binary Tree Level Order Traversal


📈 35.83 Punkte

✅ LeetCode Meditations: House Robber


📈 35.83 Punkte

✅ LeetCode Meditations — Chapter 10: Tries


📈 35.83 Punkte

✅ LeetCode Meditations: Lowest Common Ancestor of a Binary Search Tree


📈 35.83 Punkte

✅ LeetCode Meditations: Climbing Stairs


📈 35.83 Punkte

✅ LeetCode Meditations: Word Search


📈 35.83 Punkte

✅ LeetCode Meditations: Subtree of Another Tree


📈 35.83 Punkte

✅ LeetCode Meditations — Chapter 12: Dynamic Programming


📈 35.83 Punkte

✅ LeetCode Meditations: Combination Sum


📈 35.83 Punkte

✅ LeetCode Meditations: Same Tree


📈 35.83 Punkte

✅ LeetCode Meditations: Course Schedule


📈 35.83 Punkte

✅ LeetCode Meditations — Chapter 9: Backtracking


📈 35.83 Punkte

✅ LeetCode Meditations: Maximum Depth of Binary Tree


📈 35.83 Punkte

✅ LeetCode Meditations: Pacific Atlantic Water Flow


📈 35.83 Punkte

✅ LeetCode Meditations: Find Median from Data Stream


📈 35.83 Punkte

✅ LeetCode Meditations: Invert Binary Tree


📈 35.83 Punkte

✅ LeetCode Meditations: Clone Graph


📈 35.83 Punkte

✅ LeetCode Meditations — Chapter 8: Heap/Priority Queue


📈 35.83 Punkte











matomo

Datei nicht gefunden!