References: 1) YouTube channel - My Code School

Tree Terminologies

Tree is an Abstract Data Type / Data Structure that simulates a hierarchial tree structure with a root node. The root node may have its child nodes, and the child nodes may have their own child nodes. Each node consists of a value and a list of references to child nodes.

Root - The topmost node in the tree is called as root, and root node is the only node without a parent.

Node 1 is the root node.

Parent - Child Relationship - If a node has a direct relationship with another node, then we can say that there is a parent-child relationship between the nodes.

Node 2 and Node 3 are children of parent Node 1

Node 4 and Node 5 are children on parent Node 2

Leaf Nodes - Nodes with no children are called as leaf nodes.

Nodes 8, 9, 5, 11 and 7 are leaf nodes as they don't have any children.

Siblings - Nodes with same parent are called as siblings.

Nodes 4 and 5 are siblings, as they have same parent - Node 2

Ancestor Nodes - If we can go from Node A to Node B, then A is ancestor of B

Since we can go from Node 1 to Node 11 via 1 -> 3 -> 6 -> 10 -> 11, all the nodes 1, 3, 6 and 10 are ancestors of Node 11.

Descendent Nodes - If we can go from Node A to Node B, then B is descendent of A.

Since we can go from Node 1 to Node 11 via 1 -> 3 -> 6 -> 10 -> 11, Node 11 is the descendent of all the nodes 1, 3, 6 and 10

Edge - If we can go from Node A to Node B, then there is a link / edge between the 2 nodes.

If a tree has n nodes, then there are exactly n-1 edges in that tree.

Depth of a Node - It is defined as number of edges in the path starting from root to the node.

Depth of root node is always 0

Depth of Node 9 is 3. (Edge 1-2 --> Edge 2-4 --> Edge 4-9)

Height of a Node - It is defined as number of edges in longest path from that node to a leaf.

Height of leaf nodes are always 0

Root of a node is NOT always equal to its depth. The height and depth of a node may or may not be equal.

Maximum depth of a tree = Height of a tree

Applications of Trees in Computer Science

• Storing naturally hierarchical data. E.g. File System
• Organization of data for quick search, insert or delete. E.g. Binary Search Trees
• Tries - Used for dynamic spell checking, used for creating dictionaries