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 relationship 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 childs.
- Leaf: is the last node of the binary tree, they don’t have any child.
- Height: The height x is the number of edge 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 same.
A Binary Tree can be:
- Full: is a binary tree in which all nodes have at least two nodes expect the leaf.
- Perfect: is a binary tree in which all the internal nodes have 2 child and the leaf are at the same level.
- Complete: is a binary tree in which all the levels are completely 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 child.
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) which have only one way to traverse them, trees can be traversed in different ways. You can traverse a binary tree by following two methods breadth-first search and depth-first search. Each of 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 make a quick overview of what’s a binary tree, 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 🔺
