Cookie Consent by Free Privacy Policy Generator 📌 LeetCode Meditations: Validate Binary Search Tree


✅ LeetCode Meditations: Validate Binary Search Tree


💡 Newskategorie: Programmierung
🔗 Quelle: dev.to

The description for Validate Binary Search Tree is:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

For example:

Example image 1

Input: root = [2, 1, 3]
Output: true

Or:

Example image 1

Input: root = [5, 1, 4, null, null, 3, 6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Even though this one looks easy to solve recursively, there is a catch.

Let's say we naively wrote something like this:

function isValidBST(root: TreeNode | null): boolean {
  if (root === null) {
    return true;
  }

  if (
    (root.left !== null && root.left.val >= root.val) ||
    (root.right !== null && root.right.val <= root.val)
  ) {
    return false;
  }

  return isValidBST(root.left) && isValidBST(root.right);
}

This would return true for the second example above, which is wrong. In that example, although the right subtree is valid in its own right, the whole tree itself is not a valid binary search tree because 3 should be in the left subtree of the root.

So, let's look at a proper solution in TypeScript, adapted from NeetCode's explanation:

/**
 * 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 isValidBST(root: TreeNode | null): boolean {
  function valid(node: TreeNode | null, left: number, right: number) {
    if (node === null) {
      return true;
    }

    if (node.val >= right || node.val <= left) {
      return false;
    }

    return valid(node.left, left, node.val) && valid(node.right, node.val, right);
  }

  return valid(root, -Infinity, Infinity);
}

Here, we give boundaries for the left and right values that we're going to check a node's value against. Here, the value should be greater than left, and less than right. We start with negative and positive infinity because the root can be any value.

Inside valid, we only update the right boundary for the left child, and we only update the left boundary for the right child.

Note
Remember that a left child can be as small as it wants to be, as long as it's smaller than the root, so only the right boundary should be updated for it:
valid(node.left, left, node.val)

Likewise, a right child can be as large as it can be, as long as it's larger than the root. Therefore, we only update the left boundary for it:
valid(node.right, node.val, right)

Of course, we return false when BST rules are broken: if the given node's value is greater than or equal to the right boundary, or less than or equal to the left boundary.

Time and space complexity

The time complexity is going to be O(n)O(n) O(n) as we do the comparisons for each node in the tree once. The space complexity will be O(h)O(h) O(h) where hh h is the height of the tree because of the recursive function we use, as it'll create a new stack frame with each call.

The next problem is called Kth Smallest Element in a BST, which sounds exciting enough. Until then, happy coding.

...

✅ LeetCode Meditations: Validate Binary Search Tree


📈 83.05 Punkte

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


📈 66 Punkte

✅ LeetCode Meditations: Serialize and Deserialize Binary Tree


📈 59.79 Punkte

✅ LeetCode Meditations: Binary Tree Maximum Path Sum


📈 59.79 Punkte

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


📈 59.79 Punkte

✅ LeetCode Meditations: Binary Tree Level Order Traversal


📈 59.79 Punkte

✅ LeetCode Meditations: Maximum Depth of Binary Tree


📈 59.79 Punkte

✅ LeetCode Meditations: Invert Binary Tree


📈 59.79 Punkte

✅ LeetCode Meditations: Implement Trie (Prefix Tree)


📈 48.55 Punkte

✅ LeetCode Meditations: Subtree of Another Tree


📈 48.55 Punkte

✅ LeetCode Meditations: Same Tree


📈 48.55 Punkte

✅ 1038. Binary Search Tree to Greater Sum Tree


📈 42.94 Punkte

✅ BST (Binary Search Tree) and AVL Tree, Data Structures: (Trees, Part II)


📈 42.94 Punkte

✅ Difference between Binary Search Tree and AVL Tree


📈 42.94 Punkte

✅ LeetCode Meditations: Word Search II


📈 42.01 Punkte

✅ LeetCode Meditations: Design Add and Search Words Data Structure


📈 42.01 Punkte

✅ LeetCode Meditations: Word Search


📈 42.01 Punkte

✅ [623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/)


📈 41.25 Punkte

✅ #Leetcode 1361: Validating Binary Tree Nodes (Medium)


📈 39.74 Punkte

✅ LeetCode Day18 Binary Tree Part 8


📈 39.74 Punkte

✅ LeetCode Day 17 Binary Tree Part 7


📈 39.74 Punkte

✅ LeetCode Day16 Binary Tree Part 6


📈 39.74 Punkte

✅ LeetCode Day 15 Binary Tree Part 5


📈 39.74 Punkte

✅ LeetCode Day 13 Binary Tree Part 4


📈 39.74 Punkte

✅ LeetCode Day 13 Binary Tree Part 3


📈 39.74 Punkte

✅ LeetCode Day 11 Binary Tree Part 1


📈 39.74 Punkte

✅ Univalued Binary Tree | LeetCode | Java


📈 39.74 Punkte

✅ Count Good Nodes in Binary Tree | LeetCode | Java


📈 39.74 Punkte

✅ Flatten Binary Tree to Linked List | LeetCode | Java


📈 39.74 Punkte

✅ Tree data structures in Rust with tree-ds (#2: Tree Operations)


📈 38.25 Punkte

✅ Search N elements in an unbalanced Binary Search Tree in O(N * logM) time


📈 36.4 Punkte

✅ LeetCode Meditations: House Robber II


📈 35.8 Punkte

✅ LeetCode Meditations — Chapter 9: Backtracking


📈 35.8 Punkte

✅ LeetCode Meditations: House Robber


📈 35.8 Punkte

✅ LeetCode Meditations: Find Median from Data Stream


📈 35.8 Punkte











matomo

Datei nicht gefunden!