Techletter #28 | May 22, 2023
What are trees?
A tree is a non-linear data structure. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero, one or more subtrees.
Two important properties of a tree are:
-
A tree has a distinguished node called
root -
Every node except the root node is connected to another node by a directed edge that is from
parent -> children.
Some of the must-know terms
-
Height: Distance between the farthest leaf to the root. Simply count the edges.
-
Depth: Distance between the node and the root.
What is a binary tree?
A binary tree is a type of tree in which each node can have at most two child nodes, known as the left child and the right child.
A
/ \
B C
/ \ \
D E F
There are different types of binary trees:
-
Full Binary Tree
-
Complete Binary Tree
-
Perfect Binary Tree
What is the difference between a binary tree and a binary search tree?
In a binary tree, each node can have at most two child nodes: a left child and a right child. The ordering of nodes in a binary tree is not based on any specific criteria or property. Whereas in a Binary Search Tree: the left child will always be less than the parent node and the right child is always greater than the parent node.
// Binary tree
A
/ \
B C
/ \ \
D E F
// Binary Search Tree
5
/ \
3 8
/ \ \
2 4 9
There are different tree traversal techniques:
-
Pre-order, In-order, and Post-order Traversal: Traverse the tree in different orders (root-left-right, left-root-right, and left-right-root).
-
Level Order Traversal: Traverse the tree level by level, from left to right.
In the upcoming articles lets go through concepts like:
Implementation of Binary Tree, Binary Search Tree, Balanced Binary Tree, Tree traversal, Trie, & Heap.