Binary Tree Traversals, Binary/Expression Trees, Binary Search Tree, Balanced Tree

Week 10, 11, 12

Traversal

Any process for visiting all of the nodes in some order

Recursive Solution and Iterative Solution

Two ways of implementing traversal

PreOrder Traversal

Visit each node before its children. Node > Left > Right

InOrder Traversal

Each node is processed between subtrees. Left > Node > Right

PostOrder Traversal

Each node is processed after subtrees traversal. Left > Right > Node

Level Order Traversal

Tree is traversed by each level. Similar to Breadth First Search

Spiral/Zigzag Level Order Traversal

Tree is traversed in spiral shape

Reverse Level Order Traversal

Visit last level first, then second last and eventually first level

Left Edge Nodes > Leaf Nodes > Right Edge Node (Bottom to Top)

Traverse boundary of binary tree.

Binary Expression Trees

A specific kind of binary tree used to represent expressions

Operands

Leaves Nodes (leaf node of the tree)

Operators

In Binary Expression Tree, it is also known as Internal Nodes

Infix

Binary Expression Tree: Left Child > Root Node > Right Child

Prefix

Binary Expression Tree: Root Node > Left Child > Right Child

Postfix

Binary Expression Tree: Left Child > Right Child > Root Node

Binary Search Tree

A node-based binary tree data structure

Print nodes at given level

BST Operations :: prints all the nodes at a particular level

Print all leaf nodes

BST Operations :: A node is a leaf node if both left and right child nodes of it are NULL

Right view of BST

BST Operations :: Set of nodes visible when tree is visited from right side

Left view of BST

BST Operations :: Set of nodes visible when tree is visited from left side

Height of BST

BST Operations :: Recursively calculated using the height of left and right subtrees of the node and assigns height to the node as max of the heights of two children plus 1

Delete node of BST

BST Operations :: Used to delete a node with specific key from the BST and return the new BST

Smallest Node of the BST

BST Operations :: Used to return the node with the smallest value in the tree

Total number of nodes in BST

BST Operations :: Returns the total count of nodes in the BST

Delete a BST

BST Operations :: Used to completely delete the BST and deallocate the memory

Balanced Tree

Follows the condition: The absolute difference of heights of left and right subtrees at any node is less than 1

Height Balanced Tree

Binary tree that is balanced based on the height of the subtrees.

Self-Balancing BST ; At every node, the absolute value if the difference in heights of the left and right subtrees is no larger than one

Weight Balanced BST

Binary tree that is balanced based on the weight on the edges of the tree.

For each node the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree

Left Edge Nodes, Leaf Nodes, Right Edge Nodes

Boundary traversals three essential parts