Thread by @swapnakpanda

Tree, Binary Tree and Binary Search Tree

Know the difference. 👇

0️⃣ Introduction to a Tree

✪ A Tree is a data structure where each element is called as a "Node".

✪ Unlike a Linked List, a Node in a Tree can point many (child) nodes.

✪ The first node from which traversal begins is called the Root Node.

++

✪ Each child node can be root of a separate tree. Each such trees are known as "Subtrees" of a given node.

✪ The number of parents, a node can have is called its "In-Degree" and it is always 1.

✪ The number of children, a node can have is called its "Out-Degree".

1️⃣ General Tree

✪ In a general tree, each node can have "0 to n" child nodes.

✪ There can be "n" number of subtrees for any node.

✪ Out-Degree can be "0 to n".

✪ Ordering of child nodes is not of high importance and, thus not guaranteed.

2️⃣ Binary Tree

✪ In a binary tree, each node can have maximum 2 child nodes.

✪ There can be 2 subtrees for any node (left subtree and right subtree)

✪ Out-Degree is between 0 to 2.

✪ Ordering of child nodes is possible (by comparing with the parent node value).

3️⃣ Binary Search Tree

Binary Search Tree is a Binary Tree with below criteria

✪ The left subtree of a node contains only nodes with values lesser than the node’s value.

✪ The right subtree of a node contains only nodes with values greater than the node’s value.

++

✪ The left and right subtree each must also be a "Binary Search Tree".

✪ There must be no nodes containing same values.

✪ Insertion/Deletion/Accessing of a node in a Binary Search Tree is faster most of the occasions.