Medium — Binary Tree | Depth-First Search | Recursion | Tree Traversal

The Problem

Given the root of a binary tree, determine if it is a valid binary search tree where all left descendants are less than the node and all right descendants are greater than the node.

Approach

This solution uses in-order traversal of the binary tree, which visits nodes in ascending order for a valid BST. During traversal, it maintains the previous node’s value and ensures each current node is strictly greater than the previous one.

Time: O(n) · Space: O(h)

Code

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def inorder_traversal(node, prev):
            if not node:
                return True

            if not inorder_traversal(node.left, prev):
                return False

            if prev[0] is not None and node.val <= prev[0]:
                return False
            prev[0] = node.val

            return inorder_traversal(node.right, prev)

        prev = [None]
        return inorder_traversal(root, prev)

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment