Data Structures and Algorithms in Java

Trees

What is a Tree?

• A tree is an abstract model of a hierarchical structure consisting of nodes with a parent-child relation.
• Applications include organization charts, file systems, and programming environments.
• Every node, except the root, has a unique parent.
• An empty structure is an empty tree.
• A non-empty tree consists of a root and its children, where the children are also trees.

Tree Terminology - 1

• Root: Unique node without a parent.
• Internal node: Node with at least one child.
• External (leaf) node: Node without children.
• Ancestors of a node: Parent, grandparent, etc.
• Descendants of a node: Child, grandchild, etc.
• Level of a node: The level of the root is 1; children have a level of i+1 if their father has level i.
• Sub-tree: Tree consisting of a node and its descendants.
• Height of a tree: Maximum level in a tree; a single node tree has a height of 1, and an empty tree has a height of 0.
• Height of a node p is the height of the sub-tree with root p. The height of a tree is the maximum number of nodes on a path from the root to a leaf node.

Tree Terminology - 2

• Degree (order) of a node: Number of its non-empty children.
• Each node is reachable from the root through a unique sequence of arcs (edges), called a path.
• The number of arcs in a path is called the length of the path.

Ordered Trees

• A tree is ordered if there is a meaningful linear order among the children of each node.

Tree Traversals

• Tree traversal is the process of visiting each node in the tree exactly one time.

Pre-order Traversal

• A node is visited before its descendants.
• Algorithm: visit(v), for each child w of v, preorder(w).

Post-order Traversal

• A node is visited after its descendants.
• Algorithm: for each child w of v, postOrder(w), visit(v).

Breadth-first Traversal

• A node is visited first, then all its children, then all its grandchildren, and so on.
• Algorithm: visit(v), visit all children v1, v2,… of v, visit all children of v1, then all children of v2, etc.

Binary Trees

• A binary tree is a tree in which each node has at most two children, designated as either a left child or a right child. An empty tree is also a binary tree.

Types of Binary Trees

• Proper Binary Tree: Every node other than the leaves has two children.
• Complete Binary Tree: All non-terminal nodes have both children, and all leaves are at the same level.

Binary Tree Traversals

Breadth-first Traversal

• Visiting each node starting from the lowest (or highest) level and moving up (or down) level by level, from left to right (or right to left).

Depth-First Traversals

• Pre-order (NLR): Visit node, then left child, then right child.
• In-order (LNR): Visit left child, then node, then right child.
• Post-order (LRN): Visit left child, then right child, then node.

Construct Binary Tree from given traversals

• Can construct a tree from inorder & preorder or inorder & postorder traversals.
• In a Preorder sequence, leftmost element is the root of the tree.
• By searching the root in Inorder sequence, we can find out all elements on left side of the root are in left subtree and elements on right are in right subtree.

Implementing Binary Trees - 1

• Binary trees can be implemented as arrays or linked structures.
• When using arrays, a node is an object with an information field and two reference fields (indexes) for the left and right children.

Implementing Binary Trees - 2

• In a linked structure, a node is an object with an information field and two reference fields (pointers) for the left and right children.

Breadth-First Traversal code

• Top-down, left-to-right implementation using a queue.

Depth-First Traversal code

• Implementations for preOrder, inOrder, and postOrder using recursion.

Binary Search Trees

• A node-based binary tree data structure with the following properties:
• The left subtree of a node contains nodes with keys less than the node's key.
• The right subtree of a node contains nodes with keys greater than the node's key.
• Both subtrees must also be binary search trees.
• Each node has a distinct key.
• An inorder traversal visits keys in increasing order.

Implementing Binary Search Trees

• Implementation includes methods for insert, visit, preOrder, inOrder, postOrder, search, deleteByMerging, and deleteByCopying.

Searching on Binary Search Trees

• Recursive search algorithm.

Insertion - 2

• Iterative insertion algorithm.

Deletion - 1

• Three cases:
  • The node is a leaf.
  • The node has one child.
  • The node has two children.

Deletion by Merging - 1

• Making one tree out of the two subtrees of the node and then attaching it to the node’s parent.

Deletion by Copying - 1

• Replace the key being deleted with its immediate predecessor (or successor).
• A key’s predecessor is the key in the rightmost node in the left subtree.