Tree DSA

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

linear data structures such as arrays, queues, linked lists, and stacks, the time complexity increase with the increase in the data size. But, tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

Tree Terminologies

• A tree data structure consists of nodes and edges.

• The root is considered the topmost node of the tree.

• The height of a node is the number of edges from the node to the deepest leaf.

• The depth of a node is the number of edges from the root to the node.

• The degree of a node is the total number of branches of that node.

• A collection of disjoint trees is called a forest.

Types of Trees

1. Binary Tree

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.

1. Binary Search Tree

All nodes of the left subtree are less than the root node. All nodes of the right subtree are more than the root node

1. AVL Tree

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

1. B-Tree

Tree Traversal

To perform an operation on a tree, you need to reach a specific node. The tree traversal algorithm helps in visiting a required node in the tree.

1. Inorder traversal (left, root, right)

2. Preorder traversal (root, left, right)

3. Postorder traversal (left, right, root)