Tree Data Structure Overview

A tree is a hierarchical data structure where elements (nodes) have parent-child relationships, creating a non-linear structure.

Nodes in a tree have a parent-child relationship. A parent node has one or more child nodes.

The topmost node in a tree, with no parent node. It's the starting point for navigating the tree.

A node with no children. They are the end points of branches in a tree.

A parent node has one or more child nodes connected to it. A child node is connected to a parent node.

The number of children a node has in a tree.

The highest degree of a node among all the nodes in a tree.

The distance (number of edges) from the root node to a specific node.

The distance from the root node to the deepest leaf node in the tree.

The distance from the node to the deepest leaf node in its subtree.

The height of the root node. This is equivalent to the depth of the tree.

A sequence of nodes and edges connecting one node to another.

A portion of a tree where every node is a descendant of a specific node.

A tree where each node has at most two children, labeled as a left child and a right child.

A binary tree where every node has either 0 or 2 children. No node can have only one child.

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

A binary tree where all levels are completely filled except possibly the last level, which is filled from left to right.

A binary tree where, except for one node, all nodes have only one child. The remaining node has no children.

A binary tree where the height of the left and right subtrees of every node differs by at most 1.

It allows storing and manipulating tree data in a continuous block of memory.

Allows flexible allocation of memory for nodes and can handle trees of varying sizes effectively.

Array-based trees use a fixed-sized array, while linked-based trees use pointers. Array-based trees have limited flexibility in size, while linked-based trees can grow dynamically.

A systematic way of visiting all the nodes in a tree to process their data.

A traversal method where, at each node, we explore as far down its subtree as possible before moving to the next node.

In-order, pre-order, and post-order.

Visit the left subtree first, then the root node, and finally the right subtree.

Visit the root node first, then the left subtree, and finally the right subtree.

Visit the left subtree first, then the right subtree, and finally the root node.

A traversal method where nodes are visited level by level, starting from the root and moving downward.

A binary tree where the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree.

New nodes are inserted as children of leaf nodes. The insertion process involves searching for the appropriate leaf node based on the value, and then adding the new node.

Deleting a node involves three cases: deleting a leaf node, deleting a node with one child, and deleting a node with two children. Different methods are used to handle these cases.

Binary search trees allow efficient searching, insertion, and deletion of elements.

Binary search trees are used in data structures like dictionaries, maps, and sets, where key-value pairs are stored and accessed efficiently.