Tree data structure

Node

Element in a tree

Root

The node at the top of the tree is called the root. There is only one root per tree and one path from the root node to any node.

Parent

Any node except the root node has one edge upward to a node called the parent.

Child

The node below a given node connected by its edge downward is called its child node.

Subtree

Subtree represents the descendants of a node.

Visiting

Visiting refers to checking the value of a node when control is on the node.

Traversing

Traversing means passing through nodes in a specific order.

Levels

The Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

Keys

The key represents a value of a node based on which a search operation is to be carried out for a node.

Leaf nodes:

Leaf nodes are nodes that are on the bottom of the tree and have no children.

Node Depth:

Node depth is the number of links from the root to the node.

Tree Height:

Tree height is the number of links from its root to the furthest leaf. The tree height is the same as the maximum node depth.