How to Validate a Binary Search Tree?

in #programminglast month
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.

Check with Range

We can check the root's value within a valid range (see https://helloacm.com/teaching-kids-programmaing-recursive-algorithm-to-validate-a-binary-search-tree/:

        def f(root, minv, maxv):
            if not root:
                return True
            if root.val <= minv or root.val >= maxv:
                return False
            return f(root.left, minv, root.val) and f(root.right, root.val, maxv)
        
        return f(root, -inf, inf)

Inorder Traversal

We can perform inorder traversal algorithm and then record the last visited node.

        prev = None
        
        def dfs(root):
            nonlocal prev
            if not root:
                return True
            if not dfs(root.left):
                return False
            if prev and prev.val >= root.val:
                return False
            prev = root
            return dfs(root.right)
            
        return dfs(root)
Sort:  

1 STEEM Power: 1805.188 VESTS
steem_to_sbd: 0.265
sbd_to_steem: 3.773584905660377
sbd_median_price: 0.265
steem_per_mvests: 553.9615306531724
vests_to_sp: 0.0005539589767778251
sp_to_vests: 1805.1795019428632
ticker.latest: 0.08371246587807098
ticker.lowest_ask: 0.08487946834557537
ticker.higest_bid: 0.08487163165711861
ticker.steem_volume: 9458.626 STEEM
ticker.sbd_volume: 800.876 SBD
Time: 2022-08-13T07:28:11.811Z


command: !price is powered by witness @justyy and his contributions are: https://steemyy.com
More commands are coming!

Coin Marketplace

STEEM 0.23
TRX 0.06
JST 0.025
BTC 19080.00
ETH 1337.70
USDT 1.00
SBD 2.56