What are the defining properties of binary tree shapes and binary search trees?

"Binary trees can be any ragged old shape, like our Figure 5.17 example. Sometimes, though, we want to talk about binary trees with a more regular shape, that satisfy certain conditions. In particular, we’ll talk about three special kinds: full binary tree. A full binary tree is one in which every node (except the leaves) has two children. Put another way, every node has either two children or none: no stringiness allowed. Figure 5.17 is not full, but it would be if we added the three blank nodes in Figure 5.21. By the way, it isn’t always possible to have a full binary tree with a particular number of nodes. For instance, a binary tree with two nodes, can’t be full, since it inevitably will have a root with only one child. A complete binary tree is one in which every level has all possible nodes present, except perhaps for the deepest level, which is filled all the way from the left. Figure 5.21 is not complete, but it would be if we fixed it up as in Figure 5.22. Unlike full binary trees, it is always possible to have a complete binary tree no matter how many nodes it contains. You just keep filling in from left to right, level after level. A perfect binary tree is simply one that is exactly balanced: every level is completely filled. Figure 5.22 is not perfect, but it would be if we either added nodes to fill out level 4, or deleted the unfinished part of level 3, as in Figure 5.23. Perfect binary trees obviously have the strictest size restrictions. It’s only possible, in fact, to have perfect binary trees with 2^(h+1) − 1 nodes, if h is the height of the tree. So there are perfect binary trees with 1, 3, 7, 15, 31, ... nodes, but none in between. In each such tree, 2^h of the nodes (almost exactly half) are leaves. Binary trees can possess some pretty amazing powers if the nodes within them are organized in certain ways. Specifically, a binary search tree and a heap are two special kinds of binary trees that conform to specific constraints. In both cases, what makes them so powerful is the rate at which a tree grows as nodes are added to it. Suppose we have a perfect binary tree. To make it concrete, let’s say it has height 3, which would give it 1+2+4+8=15 nodes, 8 of which are leaves. Now what happens if you increase the height of this tree to 4? If it’s still a “perfect” tree, you will have added 16 more nodes (all leaves). Thus you have doubled the number of leaves by simply adding one more level. This cascades the more levels you add. A tree of height 5 doubles the number of leaves again (to 32), and height 6 doubles it again (to 64). The reason this is called “exponential” growth is that the quantity we’re varying—the height—appears as an exponent in the number of leaves, which is 2^h. Every time we add just one level, we double the number of leaves. So the number of leaves, call it l, is 2^h, if h is the height of the tree. Flipping this around, we say that h = lg(l). The function “lg” is a logarithm, specifically a logarithm with base-2. Since 2^h grows very, very quickly, it follows that lg(l) grows very, very slowly. After our tree reaches a few million nodes, we can add more and more nodes without growing the height of the tree significantly at all. The takeaway message here is simply that an incredibly large number of nodes can be accommodated in a tree with a very modest height. This makes it possible to, among other things, search a huge amount of information astonishingly quickly—provided the tree’s contents are arranged properly. A binary search tree (BST) is any binary tree that satisfies one additional property: every node is “greater than” all of the nodes in its left subtree, and “less than (or equal to)” all of the nodes in its right subtree. We’ll call this the BST property. The phrases “greater than” and “less than” are in quotes here because their meaning is somewhat flexible, depending on what we’re storing in the tree. If we’re storing numbers, we’ll use numerical order. If we’re storing names, we’ll use alphabetical order. Whatever it is we’re storing, we simply need a way to compare two nodes to determine which one “goes before” the other. An example of a BST containing people is given in Figure 5.24. Imagine that each of these nodes contains a good deal of information about a particular person—an employee record, medical history, account information, what have you. The nodes themselves are indexed by the person’s name, and the nodes are organized according to the BST rule. Mitch comes after Ben/Jessica/Jim and before Randi/Owen/Molly/Xander in alphabetical order, and this ordering relationship between parents and children repeats itself all the way down the tree. Be careful to observe that the ordering rule applies between a node and the entire contents of its subtrees, not merely to its immediate children. Your first inclination, when glancing at Figure 5.25, below, is to judge it a BST. It is not a binary search tree, however! Jessica is to the left of Mitch, as she should be, and Nancy is to the right of Jessica, as she should be. It seems to check out. But the problem is that Nancy is a descendant of Mitch’s left subtree, whereas she must properly be placed somewhere in his right subtree. And yes, this matters. So be sure to check your BSTs all the way up and down. The key insight is to realize that if you’re looking for a node, all you have to do is start at the root and go the height of the tree down making one comparison at each level. Let’s say we’re searching Figure 5.24 for Molly. By looking at Mitch (the root), we know right away that Molly must be in the right subtree, not the left, because she comes after Mitch in alphabetical order. So we look at Randi. This time, we find that Molly comes before Randi, so she must be somewhere in Randi’s left branch. Owen sends us left again, at which point we find Molly. With a tree this size, it doesn’t seem that amazing. But suppose its height were 10. This would mean about 2000 nodes in the tree—customers, users, friends, whatever. With a BST, you’d only have to examine ten of those 2000 nodes to find whatever you’re looking for."