DSA #4 Binary Tree and Binary Search Tree
A Binary tree is a tree whose elements have at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
Advantage
- Provide a hierarchical way of storing data
- allows insertion, deletion, and searching operations that yield faster than an array or linked list
- reflects structural relationships in data set
Binary Tree Terminologies
- Root: the entry point. the root is the main node of the binary tree it doesn’t have a parent node.
- Child: is a node with an incoming link from an upper node i.e. a parent node. A child can only have one parent.
- Parent: is a node with an outgoing link to a lower node, i.e. child node. A parent node can have at least 0 child or at most 2 children.
- Leaf: is the last node of the binary tree, they don’t have any child.
- Height: The height x is the number of edges in the longest path between this node and the root. The height of a tree is equivalent to the height of the node with the maximum edges.
- Sibling: Two nodes are said to be siblings if they are present at the same level, and their parents are the same.
A Binary Tree can be:
- Full: is a binary tree in which all nodes have at least two nodes except the leaf.
- Perfect: is a binary tree in which all the internal nodes have 2 children and the leaf is at the same level.
- Complete: is a binary tree in which all the levels are filled except possibly the lowest one, which is filled from the left.
Difference between Binary Tree and Binary Search Tree
A Binary Search Tree is a node-based binary tree in which every left child has a smaller value than its parent, every right child has a larger value than its parent and each node contains at most 2 children.
How to implement a Binary Search Tree in javaScript
First, you need to create a class for each node:
Next, create the Tree class as follows:
Insert a new node
To insert a node into a binary search tree, first we create a new node, we check if there is a root in it, if not, the new node becomes the root, if there is a root, we compare the new node with the root, if it’s greater than the root, check to see if there is a node to the right of the root, if not, add the new node as the right property, if there is, move to the right node and repeat these steps. If the new node is less than the root, check to see if there is a node to the left of the root, if not, add the new node as the left property, if there is, move to the left node and repeat these steps.
How to traverse a binary tree
Unlike linear data structures (array, linked list, Queues, stack) with only one way to traverse them, trees can be traversed differently. You can traverse a binary tree by following two methods breadth-first search and depth-first search. These topics will be discussed in the various posts in the rest of this series.
We are at the end of this post, where we quickly overview what a binary tree is and the difference between a binary tree and a binary search tree. In the next post, we will discuss the breadth-first search algorithm. Hope you learn something new.
The Nothing 🔺
