Binary Trees and Tree Traversals

Hello students, welcome to Kwickprep. The same six numbers can be read from one tree in three different orders. Which order gives them sorted? By the end of this lesson, you will know. Today we learn tree terms, pre order, in order and post order traversal, the binary search tree, and typical exam questions.

First, what is a tree in computing? Think of a family tree, or folders inside folders on a computer. A tree stores data in levels, starting from one node at the top. Each node can have children below it, joined by lines called edges. A binary tree is a tree where each node has at most two children, called the left child and the right child.

We will use this tree for the whole lesson, so draw it in your notebook. Fifty is at the top, with thirty on its left and seventy on its right. Thirty has two children, twenty on the left and forty on the right. Seventy has no left child, and eighty on its right. Twenty, forty and eighty have no children at all.

Now the terms, one by one. The root is the top node, with no parent, so here it is fifty. A parent is the node just above, and a child is the node just below, so thirty is the parent of twenty. Siblings are nodes with the same parent, like twenty and forty. A leaf is a node with no children, so twenty, forty and eighty are leaves. An internal node has at least one child, like fifty, thirty and seventy.

Five more terms that exams ask. The degree of a node is its number of children, so seventy has degree one. The level of the root is zero, its children are level one, and so on, so forty is at level two. The depth of a node is the number of edges from the root, so forty has depth two. The height of the tree is the number of edges on the longest path from root to a leaf, which is two. The size is the number of nodes, which is six.

Traversal means visiting every node exactly once, in a fixed order. In pre order, visit the root first, then the left subtree, then the right subtree. A subtree is a node together with everything below it. In order visits the left subtree, then the root, then the right subtree. Post order visits the left subtree, then the right subtree, and the root last. The word pre, in or post tells you where the root goes.

Let us animate pre order, root, left, right. Step one, we are at the root, so we print fifty first. Step two, we go to the left subtree, and print its root, thirty. Step three, we finish thirty's subtree, printing twenty, then forty. Step four, we go to the right subtree and print seventy. Step five, seventy has no left child, so we print eighty. Pre order is fifty, thirty, twenty, forty, seventy, eighty.

Now in order, left, root, right. Step one, we keep going left from fifty to thirty to twenty, and print twenty. Step two, we come back and print thirty, then its right child forty. Step three, the whole left subtree is done, so we print the root, fifty. Step four, in the right subtree we print seventy, then eighty. In order is twenty, thirty, forty, fifty, seventy, eighty, which is sorted!

Finally post order, left, right, root. Step one, in the left subtree, we print thirty's children first, twenty and forty. Step two, only then we print thirty. Step three, in the right subtree, we print eighty before its parent seventy. Step four, the root fifty is printed last. Post order is twenty, forty, thirty, eighty, seventy, fifty.

Traversals are short in Java because they use recursion. Here each Node has data, a left link and a right link. The base case says, if r is null, there is nothing to visit, so return. Then we visit the left subtree, print the data, and visit the right subtree. Move the print line to the top for pre order, or to the bottom for post order.

Our tree is special, because it is a binary search tree, or BST. In a BST, every value in the left subtree is smaller than the node. Every value in the right subtree is greater than the node. To search forty, it is less than fifty, so go left, and more than thirty, so go right, and we find it. To insert sixty, it is more than fifty, so go right, and less than seventy, so it becomes seventy's left child. That is why in order traversal of a BST prints values in sorted order.

Pause the video and answer these four exam style questions about our tree. First, the leaves are the nodes with no children, twenty, forty and eighty. Second, node thirty has two children, so its degree is two. Third, the longest path from the root to a leaf has two edges, so the height is two. Fourth, post order is twenty, forty, thirty, eighty, seventy, fifty.

Here are some tips for tree questions. Always draw the tree neatly before answering. Some textbooks count height in nodes instead of edges, or start the root at level one. So write one line saying which convention you follow, and follow your textbook. Also remember, level L of a binary tree can hold at most two to the power L nodes, with the root at level zero.

Let us revise. The root is at the top, and leaves have no children. Degree counts children, while depth and height count edges. Pre order is root, left, right, in order is left, root, right, and post order is left, right, root. In a binary search tree, smaller values go left and greater values go right. And in order traversal of a BST gives sorted order.