Binary Search Trees

from collections import deque


class TreeNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None


def build_tree(values: list[int | None]) -> TreeNode | None:
    """Builds a tree from level-order values, where None marks a missing child.
    This is how LeetCode writes trees down."""
    first = values[0] if values else None
    if first is None:
        return None
    root = TreeNode(first)
    queue = deque([root])
    i = 1
    # Hand out the remaining values two at a time, left child then right, to
    # the nodes in the order they were created.
    while i < len(values):
        node = queue.popleft()
        left = values[i]
        if left is not None:
            node.left = TreeNode(left)
            queue.append(node.left)
        i += 1
        right = values[i] if i < len(values) else None
        if right is not None:
            node.right = TreeNode(right)
            queue.append(node.right)
        i += 1
    return root


def is_valid(node: TreeNode | None, low: int | None, high: int | None) -> bool:
    """Whether every value in the subtree at `node` lies strictly between `low`
    and `high` (None means no bound), with the same rule holding all the way down."""
    if node is None:
        return True
    if (low is not None and node.val <= low) or (high is not None and node.val >= high):
        return False
    # The left subtree must also stay below this node, and the right one above it.
    return is_valid(node.left, low, node.val) and is_valid(node.right, node.val, high)


def is_valid_bst(root: TreeNode | None) -> bool:
    """Whether the tree is a binary search tree: at every node, the whole left
    subtree is smaller and the whole right subtree is larger."""
    return is_valid(root, None, None)


if __name__ == "__main__":
    print(is_valid_bst(build_tree([2, 1, 3])))  # True
    print(is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6])))  # False
    print(is_valid_bst(build_tree([5, 4, 6, None, None, 3, 7])))  # False
    print(is_valid_bst(build_tree([2, 2, 2])))  # False

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

// Builds a tree from level-order values, where null marks a missing child.
// This is how LeetCode writes trees down.
function buildTree(values: (number | null)[]): TreeNode | null {
  const first = values.length > 0 ? values[0] : null;
  if (first === null) return null;
  const root = new TreeNode(first);
  const queue = [root];
  let head = 0; // Reading from a head index keeps each dequeue O(1).
  let i = 1;
  // Hand out the remaining values two at a time, left child then right, to
  // the nodes in the order they were created.
  while (i < values.length) {
    const node = queue[head++];
    const left = values[i];
    if (left !== null) {
      node.left = new TreeNode(left);
      queue.push(node.left);
    }
    i++;
    const right = i < values.length ? values[i] : null;
    if (right !== null) {
      node.right = new TreeNode(right);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

// Whether every value in the subtree at `node` lies strictly between `low`
// and `high` (null means no bound), with the same rule holding all the way down.
function isValid(node: TreeNode | null, low: number | null, high: number | null): boolean {
  if (node === null) return true;
  if ((low !== null && node.val <= low) || (high !== null && node.val >= high)) return false;
  // The left subtree must also stay below this node, and the right one above it.
  return isValid(node.left, low, node.val) && isValid(node.right, node.val, high);
}

// Whether the tree is a binary search tree: at every node, the whole left
// subtree is smaller and the whole right subtree is larger.
export function isValidBST(root: TreeNode | null): boolean {
  return isValid(root, null, null);
}

console.log(isValidBST(buildTree([2, 1, 3]))); // true
console.log(isValidBST(buildTree([5, 1, 4, null, null, 3, 6]))); // false
console.log(isValidBST(buildTree([5, 4, 6, null, null, 3, 7]))); // false
console.log(isValidBST(buildTree([2, 2, 2]))); // false

package main

import "fmt"

// TreeNode is one node of a binary tree.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// buildTree builds a tree from level-order values, where nil marks a missing
// child. This is how LeetCode writes trees down.
func buildTree(values []any) *TreeNode {
	if len(values) == 0 || values[0] == nil {
		return nil
	}
	root := &TreeNode{Val: values[0].(int)}
	queue := []*TreeNode{root}
	i := 1
	// Hand out the remaining values two at a time, left child then right, to
	// the nodes in the order they were created.
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]
		if values[i] != nil {
			node.Left = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Left)
		}
		i++
		if i < len(values) && values[i] != nil {
			node.Right = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// isValid reports whether every value in the subtree at node lies strictly
// between low and high (nil means no bound), with the same rule holding all
// the way down.
func isValid(node *TreeNode, low, high *int) bool {
	if node == nil {
		return true
	}
	if (low != nil && node.Val <= *low) || (high != nil && node.Val >= *high) {
		return false
	}
	// The left subtree must also stay below this node, and the right one above it.
	return isValid(node.Left, low, &node.Val) && isValid(node.Right, &node.Val, high)
}

// isValidBST reports whether the tree is a binary search tree: at every node,
// the whole left subtree is smaller and the whole right subtree is larger.
func isValidBST(root *TreeNode) bool {
	return isValid(root, nil, nil)
}

func main() {
	fmt.Println(isValidBST(buildTree([]any{2, 1, 3})))                 // true
	fmt.Println(isValidBST(buildTree([]any{5, 1, 4, nil, nil, 3, 6}))) // false
	fmt.Println(isValidBST(buildTree([]any{5, 4, 6, nil, nil, 3, 7}))) // false
	fmt.Println(isValidBST(buildTree([]any{2, 2, 2})))                 // false
}

using System;
using System.Collections.Generic;

public class Solution
{
    public class TreeNode
    {
        public int Val;
        public TreeNode? Left, Right;

        public TreeNode(int val) => Val = val;
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode? BuildTree(int?[] values)
    {
        if (values.Length == 0 || values[0] is not int first) return null;
        var root = new TreeNode(first);
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.Length)
        {
            var node = queue.Dequeue();
            if (values[i] is int left)
            {
                node.Left = new TreeNode(left);
                queue.Enqueue(node.Left);
            }
            i++;
            if (i < values.Length && values[i] is int right)
            {
                node.Right = new TreeNode(right);
                queue.Enqueue(node.Right);
            }
            i++;
        }
        return root;
    }

    // Whether every value in the subtree at node lies strictly between low and
    // high (null means no bound), with the same rule holding all the way down.
    static bool IsValid(TreeNode? node, int? low, int? high)
    {
        if (node == null) return true;
        if ((low != null && node.Val <= low) || (high != null && node.Val >= high)) return false;
        // The left subtree must also stay below this node, and the right one above it.
        return IsValid(node.Left, low, node.Val) && IsValid(node.Right, node.Val, high);
    }

    // Whether the tree is a binary search tree: at every node, the whole left
    // subtree is smaller and the whole right subtree is larger.
    public static bool IsValidBST(TreeNode? root) => IsValid(root, null, null);

    public static void Main()
    {
        Console.WriteLine(IsValidBST(BuildTree(new int?[] { 2, 1, 3 }))); // True
        Console.WriteLine(IsValidBST(BuildTree(new int?[] { 5, 1, 4, null, null, 3, 6 }))); // False
        Console.WriteLine(IsValidBST(BuildTree(new int?[] { 5, 4, 6, null, null, 3, 7 }))); // False
        Console.WriteLine(IsValidBST(BuildTree(new int?[] { 2, 2, 2 }))); // False
    }
}

import java.util.ArrayDeque;

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode buildTree(Integer[] values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.length) {
            TreeNode node = queue.poll();
            if (values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    // Whether every value in the subtree at node lies strictly between low and
    // high (null means no bound), with the same rule holding all the way down.
    static boolean isValid(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
        // The left subtree must also stay below this node, and the right one above it.
        return isValid(node.left, low, node.val) && isValid(node.right, node.val, high);
    }

    // Whether the tree is a binary search tree: at every node, the whole left
    // subtree is smaller and the whole right subtree is larger.
    static boolean isValidBST(TreeNode root) {
        return isValid(root, null, null);
    }

    public static void main(String[] args) {
        System.out.println(isValidBST(buildTree(new Integer[] {2, 1, 3}))); // true
        System.out.println(isValidBST(buildTree(new Integer[] {5, 1, 4, null, null, 3, 6}))); // false
        System.out.println(isValidBST(buildTree(new Integer[] {5, 4, 6, null, null, 3, 7}))); // false
        System.out.println(isValidBST(buildTree(new Integer[] {2, 2, 2}))); // false
    }
}

from collections import deque


class TreeNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None


def build_tree(values: list[int | None]) -> TreeNode | None:
    """Builds a tree from level-order values, where None marks a missing child.
    This is how LeetCode writes trees down."""
    first = values[0] if values else None
    if first is None:
        return None
    root = TreeNode(first)
    queue = deque([root])
    i = 1
    # Hand out the remaining values two at a time, left child then right, to
    # the nodes in the order they were created.
    while i < len(values):
        node = queue.popleft()
        left = values[i]
        if left is not None:
            node.left = TreeNode(left)
            queue.append(node.left)
        i += 1
        right = values[i] if i < len(values) else None
        if right is not None:
            node.right = TreeNode(right)
            queue.append(node.right)
        i += 1
    return root


def kth_smallest(root: TreeNode | None, k: int) -> int:
    """The kth smallest value in the BST (k counts from 1), or -1 if the tree has
    fewer than k values."""
    # An in-order walk with our own stack, so it can stop after k values.
    stack: list[TreeNode] = []
    node = root
    count = 0
    while node is not None or stack:
        # The smallest value not yet visited is as far left as you can go.
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        # Everything in its right subtree comes next in sorted order.
        node = node.right
    return -1


if __name__ == "__main__":
    print(kth_smallest(build_tree([3, 1, 4, None, 2]), 1))  # 1
    root = build_tree([5, 3, 6, 2, 4, None, None, 1])
    print(kth_smallest(root, 3))  # 3
    print(kth_smallest(root, 6))  # 6

class TreeNode {
  val: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(val: number) {
    this.val = val;
  }
}

// Builds a tree from level-order values, where null marks a missing child.
// This is how LeetCode writes trees down.
function buildTree(values: (number | null)[]): TreeNode | null {
  const first = values.length > 0 ? values[0] : null;
  if (first === null) return null;
  const root = new TreeNode(first);
  const queue = [root];
  let head = 0; // Reading from a head index keeps each dequeue O(1).
  let i = 1;
  // Hand out the remaining values two at a time, left child then right, to
  // the nodes in the order they were created.
  while (i < values.length) {
    const node = queue[head++];
    const left = values[i];
    if (left !== null) {
      node.left = new TreeNode(left);
      queue.push(node.left);
    }
    i++;
    const right = i < values.length ? values[i] : null;
    if (right !== null) {
      node.right = new TreeNode(right);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

// The kth smallest value in the BST (k counts from 1), or -1 if the tree has
// fewer than k values.
export function kthSmallest(root: TreeNode | null, k: number): number {
  // An in-order walk with our own stack, so it can stop after k values.
  const stack: TreeNode[] = [];
  let node = root;
  let count = 0;
  while (node !== null || stack.length > 0) {
    // The smallest value not yet visited is as far left as you can go.
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop()!;
    count++;
    if (count === k) return node.val;
    // Everything in its right subtree comes next in sorted order.
    node = node.right;
  }
  return -1;
}

console.log(kthSmallest(buildTree([3, 1, 4, null, 2]), 1)); // 1
const root = buildTree([5, 3, 6, 2, 4, null, null, 1]);
console.log(kthSmallest(root, 3)); // 3
console.log(kthSmallest(root, 6)); // 6

package main

import "fmt"

// TreeNode is one node of a binary tree.
type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// buildTree builds a tree from level-order values, where nil marks a missing
// child. This is how LeetCode writes trees down.
func buildTree(values []any) *TreeNode {
	if len(values) == 0 || values[0] == nil {
		return nil
	}
	root := &TreeNode{Val: values[0].(int)}
	queue := []*TreeNode{root}
	i := 1
	// Hand out the remaining values two at a time, left child then right, to
	// the nodes in the order they were created.
	for i < len(values) {
		node := queue[0]
		queue = queue[1:]
		if values[i] != nil {
			node.Left = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Left)
		}
		i++
		if i < len(values) && values[i] != nil {
			node.Right = &TreeNode{Val: values[i].(int)}
			queue = append(queue, node.Right)
		}
		i++
	}
	return root
}

// kthSmallest returns the kth smallest value in the BST (k counts from 1), or
// -1 if the tree has fewer than k values.
func kthSmallest(root *TreeNode, k int) int {
	// An in-order walk with our own stack, so it can stop after k values.
	stack := []*TreeNode{}
	node := root
	count := 0
	for node != nil || len(stack) > 0 {
		// The smallest value not yet visited is as far left as you can go.
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		count++
		if count == k {
			return node.Val
		}
		// Everything in its right subtree comes next in sorted order.
		node = node.Right
	}
	return -1
}

func main() {
	fmt.Println(kthSmallest(buildTree([]any{3, 1, 4, nil, 2}), 1)) // 1
	root := buildTree([]any{5, 3, 6, 2, 4, nil, nil, 1})
	fmt.Println(kthSmallest(root, 3)) // 3
	fmt.Println(kthSmallest(root, 6)) // 6
}

using System;
using System.Collections.Generic;

public class Solution
{
    public class TreeNode
    {
        public int Val;
        public TreeNode? Left, Right;

        public TreeNode(int val) => Val = val;
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode? BuildTree(int?[] values)
    {
        if (values.Length == 0 || values[0] is not int first) return null;
        var root = new TreeNode(first);
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.Length)
        {
            var node = queue.Dequeue();
            if (values[i] is int left)
            {
                node.Left = new TreeNode(left);
                queue.Enqueue(node.Left);
            }
            i++;
            if (i < values.Length && values[i] is int right)
            {
                node.Right = new TreeNode(right);
                queue.Enqueue(node.Right);
            }
            i++;
        }
        return root;
    }

    // The kth smallest value in the BST (k counts from 1), or -1 if the tree has
    // fewer than k values.
    public static int KthSmallest(TreeNode? root, int k)
    {
        // An in-order walk with our own stack, so it can stop after k values.
        var stack = new Stack<TreeNode>();
        var node = root;
        int count = 0;
        while (node != null || stack.Count > 0)
        {
            // The smallest value not yet visited is as far left as you can go.
            while (node != null)
            {
                stack.Push(node);
                node = node.Left;
            }
            node = stack.Pop();
            count++;
            if (count == k) return node.Val;
            // Everything in its right subtree comes next in sorted order.
            node = node.Right;
        }
        return -1;
    }

    public static void Main()
    {
        Console.WriteLine(KthSmallest(BuildTree(new int?[] { 3, 1, 4, null, 2 }), 1)); // 1
        var root = BuildTree(new int?[] { 5, 3, 6, 2, 4, null, null, 1 });
        Console.WriteLine(KthSmallest(root, 3)); // 3
        Console.WriteLine(KthSmallest(root, 6)); // 6
    }
}

import java.util.ArrayDeque;

public class Solution {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Builds a tree from level-order values, where null marks a missing child.
    // This is how LeetCode writes trees down.
    static TreeNode buildTree(Integer[] values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        // Hand out the remaining values two at a time, left child then right, to
        // the nodes in the order they were created.
        while (i < values.length) {
            TreeNode node = queue.poll();
            if (values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    // The kth smallest value in the BST (k counts from 1), or -1 if the tree has
    // fewer than k values.
    static int kthSmallest(TreeNode root, int k) {
        // An in-order walk with our own stack, so it can stop after k values.
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        int count = 0;
        while (node != null || !stack.isEmpty()) {
            // The smallest value not yet visited is as far left as you can go.
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            count++;
            if (count == k) return node.val;
            // Everything in its right subtree comes next in sorted order.
            node = node.right;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(kthSmallest(buildTree(new Integer[] {3, 1, 4, null, 2}), 1)); // 1
        TreeNode root = buildTree(new Integer[] {5, 3, 6, 2, 4, null, null, 1});
        System.out.println(kthSmallest(root, 3)); // 3
        System.out.println(kthSmallest(root, 6)); // 6
    }
}