The three properties describing a binary search tree are wrong! It isn’t just about a node and its two children. It’s about a node and its descendants. The properties should read:
- All descendants down the left edge of a node must have a value less than the node’s value.
- All descendants down the right edge of a node must have a value greater than the node’s value.
- These two properties hold for all nodes in the tree.
Don’t the “node-scope” rules described in the article imply the “tree-scope” phenomenon you’re describing?
The platform could have an option to favorite some topics.
Isn’t the image in the definition incorrect? 2 is less than 6 and is placed on the left branch of the node so it is a valid binary search tree?
I dont understand the return tree
2 is less than six so it is correct to have it in the left subtree of 6, BUT 2 is also less than 3, so it should also be in the left subtree of 3. The correct location for 2 is shown below:
Didn’t realize the comment would clobber my spacing and mess up my beautiful tree ASCII drawing. 2 should be the RIGHT CHILD of 1, that way 1 and 2 are both in the left subtree below 3 and 2 is in the right subtree below 1 (since 2 is greater than one but less than 3). Here’s the correct BST in algo monsters format:
8 3 1 x 2 x x 6 x x 10 x x
Can you explain return tree line more?
def insert(tree, val):
if tree is None:
if tree.val < val:
tree.right = insert(tree.right, val)
elif tree.val > val:
tree.left = insert(tree.left, val)
Very nice the end section comparing BSTs with sorted arrays and hash tables