![Free eBooks of IT [BooksOfAll]](https://www.booksofall.com/wp-content/uploads/2022/06/booksofall-logo-2.png){kind=logo}
Introduction
The problem will use two data structures — an ordered binary tree and a circular doubly linked list. Both data structures store sorted elements, but they look very different.
In the ordered binary tree, each node contains a single data element and “small” and “large” pointers to sub-trees (sometimes the two pointers are just called “left” and “right”).
Figure-1 — ordered binary tree
All the nodes in the “small” sub-tree are less than or equal to the data in the parent node. All the nodes in the “large” sub-tree are greater than the parent node. So in the example above, all the nodes in the “small” sub-tree off the 4 node are less than or equal to 4, and all the nodes in “large” sub-tree are greater than 4. That pattern applies for each node in the tree. A null pointer effectively marks the end of a branch in the tree. Formally, a null pointer represents a tree with zero elements. The pointer to the topmost node in a tree is called the “root”.
Figure-2 — doubly linked circular list
The circular doubly linked list is a standard linked list with two additional features…
“Doubly linked” means that each node has two pointers — the usual “next” pointer that points to the next node in the list and a “previous” pointer to the previous node. “Circular” means that the list does not terminate at the first and last nodes. Instead, the “next” from the last node wraps around to the first node. Likewise, the “previous” from the first node wraps around to the last node.
We’ll use the convention that a null pointer represents a list with zero elements. It turns out that a length-1 list looks a little silly…
Figure-3 — a length-1 circular doubly linked list
The single node in a length-1 list is both the first and last node, so its pointers point to itself. Fortunately, the length-1 case obeys the rules above so no special case is required.
The Trick — Separated at Birth? Here’s the trick that underlies the Great Tree-List Problem: look at the nodes that make up the ordered binary tree. Now look at the nodes that make up the linked list. The nodes have the same type structure — they each contain an element and two pointers. The only difference is that in the tree, the two pointers are labeled “small”…
