Tree Basics & Tricks
Updated:
1. Tree Properties

The depth of a node is the number of edges from the node to the tree’s root node. A root node will have a depth of 0.

The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

The height of a tree is the height of the root or the maximal depth. (For a complete binary tree, its height is Θ(lgn) )

A level or layer of a tree consists of all nodes of the same depth the number of levels is the height of the tree + 1
2. Tree normal traversal
There are several ways to implement a Tree. The most common one is using a linked data structure in which, in addition to a key and satellite data each node has left, right and parents pointers.
<1> InOrder Traversal Visit left subtree, then node itself, then right subtree
algorithm InOrderTravesal(n):
if n != NIL then
InOrderTraversal(n.left)
 only visit(print) itself when returning from the left subtree 
Visit(n)
InOrderTraversal(n.right)
Output: 2, 5, 5, 6, 7, 8
<2> PostOrder Traversal Visit all successors and next the node itself
algorithm PostOrderTraversal(n):
if m.left != NIL then
PostOrderTraversal(n.left)
if m.right != NIL then
PostOrderTraversal(n.right)
Visit(n)
 only visit(print) itself when returning from both subtree 
Output:
(Numbers represent traversal order)
<3> PreOrder Traversal First visit itself and next its successors
algorithm PreOrderTraversal(n):
Visit(n)
if m.left != NIL then
PostOrderTraversal(n.left)
if m.right != NIL then
PostOrderTraversal(n.right)
Tip:
 In my point of view, the embedded (inside) recursion functions are just entries that represent execution order. The code below an entry will not be executed until that entry was bounced back (returned).
 the
.left
and.right
for a leaf are bothNIL
so for inorder traversal, instead ofif n != NIL then ...
, we could doif n.left != NIL and n.right != NIL then ...
for the sake of intuition.  to better understand these traversal algorithms, bear in mind that the order of a given traversal method should be satisfied in every subtree.
4. Tree traversal augmentations (tricks)
There are some interesting implementations of traversing a tree structure I’d like to share:
 Nonrecursive preorder traversal:
Algorithm NonRecurPreOrder(startNode):
S := new Stack
Push(S, startNode)
While not S.isEmpty() do
node := Pop(S)
While node != NIL do:
Visit(node)
Push(S, node.right)
node := node.left
 Nonrecursuve inorder traversal:
Algorithm NonRecurInOrder(startNode):
if startNode == NIL then return
S := new Stack
Push(S, startNode)
node := startNode
While not S.isEmpty() do
While node.left != NIL do
node := node.left
Push(S, node)
node := Pop(S)
Visit(node)
 the most beatiful logic is here 
if node.right != NIL then
node := node.right
Push(S, node)
5. InOrder Traversal Time Complexcity
\(T(n) = Θ(n)\) Proof:
6. Today’s special
###Reserve singly linkedlist nonrecursively in Θ(n)
Algorithm ReserveSLL(L):
if L.head == NIL then
return
prevPtr := L.head
prevPtr.next := NIL > After revserving, L.head will becomes the new tail whose next should be NIL
currPtr := L.head.next > starts from the second node (head.next)
nextPtr := NIL
While currPtr != NIL do
nextPtr := currPtr.next
currPtr.next := prePtr
prevPtr := currPtr
currPtr := nextPtr
L.head := prevPtr > Don't forget to set the head in the end
Leave a comment