Validate Binary Search Tree | LeetCode

Problem Statement

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.

Example 1:

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

PHP Implementation

Let’s take a look at a PHP solution for validating whether a given binary tree is a valid binary search tree. We’ll use a recursive approach to traverse the tree and check the ordering property at each node.

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function isValidBST($root) {
       return $this->valid($root, PHP_INT_MIN, PHP_INT_MAX);
    }

    function valid($node, $left, $right) {
        if (empty($node)) return true;
        if (!($left < $node->val && $node->val < $right)) return false;

        return $this->valid($node->left, $left, $node->val) &&
               $this->valid($node->right, $node->val, $right);
    }
}

Explanation

We define a class TreeNode to represent nodes in the binary tree. Each node has a value, a left child, and a right child.

• Before traversing each node in the binary tree, we establish a range for it by passing lower and upper bounds as parameters to the function.
• As we visit each node, we verify if its key falls within this range.
  - If not, we immediately return false without further traversal.
  - However, if the node’s key is within the specified range, we recursively call the function for its left and right subtrees.
• Upon reaching a null node, representing the end of a branch, we return true.

The lower bound of the starting range is a minimum integer, say INT_PHP_MIN, and the upper bound is a maximum integer, say INT_PHP_MAX because the root’s key can have any value.

• Start with root(key = 5) and the set initial range. INT_PHP_MIN < 5< INT_PHP_MAX. Continue traversal.
• Arrive at node with key 2 with [INT_PHP_MIN ,5] as range. INT_PHP_MIN< 2< 5.Continue traversal.
• Arrive at a node with key 1with [INT_PHP_MIN, 2] as a range. INT_PHP_MIN< 1< 2. Continue traversal.
• Reaches NULL. Return true.
• Arrive at the node with key 3 with [2, 5] as a range. 2< 3< 5. Continue traversal.
• Reaches NULL. Return true.
• Arrive at a node with key 7with [5, INT_PHP_MAX] as the range. 5< 7< INT_PHP_MAX. Continue traversal.
• Arrive at a node with key 6with [5, 7] as the range. 5<6<7
• Arrive at node with key 4 with [5,7] as the range, 4 does not lie in the range. Do not continue traversal, return false.

Conclusion

In this article, we’ve explored the concept of binary search trees and examined a PHP implementation for validating their structure.

Happy Coding :)