A developer hand-edited a saved search index and you need to check it before loading. The index must be a valid binary search tree: for every node, every value in its left subtree is strictly smaller than the node's value, and every value in its right subtree is strictly bigger.
Write isValidIndex(root) that returns true if the tree follows that rule everywhere and false otherwise. An empty tree is valid. Note that checking each node only against its own children is not enough.
Input: root = [8,3,10,1,6] Output: true
Every left subtree is smaller and every right subtree is bigger.
Input: root = [8,3,10,1,9] Output: false
9 is in 8's left subtree but bigger than 8, even though it is bigger than its parent 3.
0 <= number of nodes <= 10000-2^31 <= value <= 2^31 - 1Trees are written level by level, like [1, 2, 3, null, 4], where null is a missing child. Your function works with TreeNode objects, each with val, left, and right.
Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #339 Validate a Search Index Tree. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.