We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
To those of you having issues with simple recursive code that just checks if the children are less/greater than the current node...
Right now, as you recurse down the tree you're going to only check if the children are "valid" with respect to their parent. But consider the following tree:
3/ \
/ \
26/\/ \
1457
You'll notice that 4 > 2 BUT 4 > 3. The number 4 should be on the right side of the tree. If you wanted it to be more like a BST it should actually look like:
3/ \
/ \
/ \
26/\/ \
14/ \
57/4
As a result, you'll want to make sure that on a given call of your function, you know what upstream "min" and "max" to compare against. Eg; with node "4" we know that the "max" on the left subtree is "3" (the root). The "min" is "1". Now, it might be tempting to do an in-order traversal of the tree to find the allowable min/max for each node. But it's simpler if you don't allow duplicates in your tree.
On a given node, left children must be at least 1 less than the current node. Right children must be at least 1 greater than the current node. We can start with a left-most bound of the smallest representable integer and a right-most bound of the largest representable integer.
Below is a super minimal solution that implements this concept.
Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
To those of you having issues with simple recursive code that just checks if the children are less/greater than the current node...
Right now, as you recurse down the tree you're going to only check if the children are "valid" with respect to their parent. But consider the following tree:
You'll notice that 4 > 2 BUT 4 > 3. The number 4 should be on the right side of the tree. If you wanted it to be more like a BST it should actually look like:
As a result, you'll want to make sure that on a given call of your function, you know what upstream "min" and "max" to compare against. Eg; with node "4" we know that the "max" on the left subtree is "3" (the root). The "min" is "1". Now, it might be tempting to do an in-order traversal of the tree to find the allowable min/max for each node. But it's simpler if you don't allow duplicates in your tree.
On a given node, left children must be at least 1 less than the current node. Right children must be at least 1 greater than the current node. We can start with a left-most bound of the smallest representable integer and a right-most bound of the largest representable integer.
Below is a super minimal solution that implements this concept.