—21—The Binary Search Tree Property
Wait,” Frank said. “That’s wrong.”
Socks, who had just finished inserting a node, looked up in surprise. “What?”
“The node you just inserted,” said Frank. “It’s in the wrong place.”
Socks peered at the tree. “But 63 is larger than 60, so it goes in the right-hand subtree.”
“But it’s greater than its great-grandparent 61, so it should have gone to that node’s right subtree. You have it down the left subtree. One of the key properties of a binary search tree is that all nodes in the left subtree are less than the current node, and all nodes in the right subtree are larger.”
“I know that,” said Socks quietly.
Get The CS Detective now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
