What is a tree data structure

Hierarchical structure that represents data in parent-child relationship.

Examples:

• Folder structure in an operating system.
• Tag structure in HTML or HXML document.

Anatomy

root

Topmost node of the tree is called a root.

• root node does NOT have a parent node.

Any nodes below a root node is considered child nodes.

parent and child

Parent nodes are immediate predecessor of a child node.

Child nodes are immediate successor of a parent node.

Child nodes can be a parent node of another child node.

These child nodes can have their own multiple child nodes, forming a recursive structure.

ancestor, descent, and sibling

Ancestor of a node are any predecessor nodes on the path of the root to that node.

A node is a descendent of another node only when that node is an ancestor of it.

Sibling(s) are childrens of the same parent node.

A level of a node is the count of edges on the path from the root node to that node (e.g. 4 nodes from root would make it a level 4).

• The root node has level 0.

leaf nodes and subtree

subtree is any node of the tree along with its descendent.

leaf node (known as external node) are any nodes that does not have any child nodes.

Implementation

Python:

# generic node
class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

# binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Javascript:

// generic tree node
class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
}

// binary tree node
class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

Different Types of Tree Data Structure

Binary Tree

• Each node can have a maximum of two children linked to it.
• Full binary trees, complete binary trees, balanced binary trees, and degenerate binary trees.
• Binary search tree and Binary heap are examples of binary tree.

Ternary Tree

• Has at most three children per node.
  • Usually distinguished as left, mid, and right.

Generic Tree

• Collection of nodes where each node is a data structure that consists of records and a list of references to its children.

Basic tree operations

Create = create a tree data structure. Insert = insert data in a tree. Search = looks for specific data in a tree. Traversal = ways to visit all the nodes in a tree.

• (see Traversal page)