TREE TERMINOLOGY

Node

Node

The fundamental part of a tree that contains data and may have links to other nodes.

Root

The topmost node of a tree. It has no parent.

Leaf

A node with no children; it is at the end of a branch.

Edge

The link between two nodes.

Parent

A node that has one or more child nodes.

Child

A node that is a descendant of another node (its parent).

Subtree

A tree formed by a node and its descendants.

Binary Tree

A tree in which each node has at most two children (left and right).

Binary Search Tree (BST)

A binary tree where each node��s left children are less than the node, and each node’s right children are greater.

Balanced Tree

A binary tree where the height difference between the left and right subtrees of any node is minimal.

Complete Binary Tree

A binary tree in which all levels are fully filled except possibly the last, and all nodes are as far left as possible.

Full Binary Tree

A binary tree in which every node has either 0 or 2 children.

Perfect Binary Tree

A binary tree where all internal nodes have exactly two children and all leaf nodes are at the same level.

AVL Tree

A self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one.

Red-Black Tree

A balanced binary search tree with additional properties to ensure balance.

Height

The length of the longest path from the root to a leaf node.

Depth

The length of the path from the root to a specific node.

Level

The level of a node is the number of edges from the root to the node. The root is at level 0.

Degree

The number of children a node has.

Pre-order Traversal

Visit the root node, then recursively visit the left subtree, followed by the right subtree.

In-order Traversal

Recursively visit the left subtree, visit the root node, then recursively visit the right subtree.

Post-order Traversal

Recursively visit the left subtree, the right subtree, and then visit the root node.

Level-order Traversal

Visit nodes level by level from the root to the leaves.

Trie

A tree-like data structure used to store a dynamic set of strings, where nodes represent prefixes of the strings.

B-Tree

A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

Segment Tree

A binary tree used for storing intervals or segments, allowing querying of segment overlaps efficiently.

In-order Successor

The node that comes immediately after a given node in in-order traversal.

In-order Predecessor

The node that comes immediately before a given node in in-order traversal.

Sibling

Nodes that share the same parent.

Ancestor

A node’s parent, grandparent, and so on up to the root.

Descendant

A node’s children, grandchildren, and so on down to the leaves.

Path

A sequence of nodes and edges connecting a node with a descendant.