Trees

Trees are recursive data structures where a node in a tree can have zero, one, or several references to other nodes and a node will have only one node referencing it. In other words, a node can have zero - many references, while a reference belongs to one node. See figure 3.1.

To have a more in-depth understanding of trees, we will examine terms to describe a tree.

Terms:

Parent - A node with references to other nodes. Every node except the root has one parent. In figure 3.1, ‘A’ is the parent of ‘B’ and ‘C’.

Child - A node is a child of any node that references it. In figure 3.1, ‘B’ and ‘C’ are children of 'A'.

Descendant - All the nodes that can be reached by traversing a path of children from a specific node. In figure 3.1, ‘D, E, F, H, I, J, K’ are descendants of ‘B’

Ancestor - Given a descendant all nodes that recursively have a common parent are ancestors. In figure 3.1, ‘A, B, D’ are ancestors of ‘I’

Leaves - Nodes that do not have any children. In figure 3.1, ‘E, G, H, I, K’ are leaves.

Binary Search Tree
in-Action with Alto.js

Binary Search Tree (BST) is a common way of storing data. In a BST, the value held by a node’s left child is less than or equal to the value of itself and the value held by a node’s right child is greater than or equal to the value of itself.

Our data structure to describe a node in a BST will be a javascript object literal. Specifically, our node will have three properties: data, left and right.

Once we have our BST generated, we will be able to traverse, find a node, find all descendants, find ancestors, and more.

We will start be exploring our traversing options.

Depth First Traversals with Binary Search Tree:

Preorder - Traverses a tree starting with the provided node, then all the left descendants and last all of the right descendants. Meaning, a node is always visited before any of its children. (self, left, right). Preorder traversal will visit our tree in figure 3.3 in the following order: (24, 11, 1, 8, 4, 5, 18, 84, 36)

Inorder - Traverses a tree starting with the provided node’s left descendants, then on the node itself, followed by the node’s right descendants. Meaning, the left subtree is visited first, then the node itself, and then the node’s right subtree. (left, self, right). Inorder traversal will visit our tree in figure 3.3 in the following order: (1, 4, 5, 8, 11, 18, 24, 36, 84)

Postorder - Traverses a tree starting with the provided node’s left descendants, then on the nodes right descendants, and finally on the node itself. Meaning, a node is always visited after its children. (left, right, self). Postorder traversal will visit our tree in figure 3.3 in the following order: (5, 4, 8, 1, 18, 11, 36, 84, 24)

Preorder

Inorder

Postorder

With our three depth first search algorithms explored, we can now perform other search actions on our binary search tree.

By modifying the logic of a preorder traversal, we can now find all leaves in our tree. When we visit “self” or the current node given, we check to see if the node has a left and right non-null data value. If true, then we found a leaf. Otherwise we call our findLeaves method again when there is a value for either node.left, node.right or both.

Checking for descendants of a given node is straight forward as well. Much like findLeaves, findDescendants uses a preorder traversal and when the root data matches our lookup, we can simply pass the matched node to our preorderTraversal method to walk the remaining nodes.

To find all ancestors of a given node. We check to see if the current nodes data is less than or greater than our lookup value. If it is less than, we move root to root.left and when it is greater than, we move out root to root.right. Before we move out root reference, we get the current value of root and push it into our ancestors array. When there is a match found, we return our ancestors.

Breadth First Traversal with Binary Search Tree:

A Breadth First Search is a bit more involved but once it is demystified its elegance is evident in its simplicity. BSF visits our tree in levels or rows.

On first traversal, we start with 24. On the next traversal we will be at level two. We visit level two in the following order, 11, 84. Then for the next traversal we will visit all of the level three nodes. Here 1, 18, 36 will be visited. And so forth.

To handle a breadth first traversal, we will need to use a queue and processed queue. Recursively visiting nodes, on the first traversal our queue will be [24] and the processed queue will be [24] as well. On the second traversal our queue will be [11, 84] and the processed queue will be [24, 11].