Binary Tree Basics and Different Views

A binary tree is a fundamental data structure in computer science and programming. It consists of nodes, where each node has at most two children, called left and right child. The topmost node is known as the root node, while the nodes without any children are called leaves. Binary trees have many applications in computer science, including searching, sorting, and storing hierarchical data.

In this blog, we will discuss the basics of binary trees and some different views of binary trees.

Binary Tree Basics:
A binary tree is a recursive data structure. It can be defined as an ordered tree in which each node has at most two children. Each node in a binary tree contains three parts: a data value, a left child, and a right child.

Traversal:

Traversing a binary tree means visiting every node of the tree in a specific order. There are three popular ways to traverse a binary tree:

• Inorder traversal: In this traversal, we first visit the left child, then the current node, and finally the right child. This traversal is used to print the values of the binary tree in ascending order.

var inorderTraversal(root){
  let result = [];
  function inorder(node){
    if(node.left) inorder(node.left)
    result.push(node.val);
    if(node.right) inorder(node.right)
  }
  if(root) inorder(root);
  return result;
}

• Preorder traversal: In this traversal, we first visit the current node, then the left child, and finally the right child.

var preorderTraversal(root){
  let result = [];
  function preorder(node){
    result.push(node.val);
    if(node.left) preorder(node.left)
    if(node.right) preorder(node.right)
  }
  if(root) preorder(root);
  return result;
}

• Postorder traversal: In this traversal, we first visit the left child, then the right child, and finally the current node.

var postorderTraversal(root){
  let result = [];
  function postorder(node){
    if(node.left) postorder(node.left)
    if(node.right) postorder(node.right)
    result.push(node.val);
  }
  if(root) postorder(root);
  return result;
}

Different Views of Binary Trees:

Binary trees can be viewed from different angles, and each view has its own significance. Some of the common views are:

• Left View: In the left view of a binary tree, we see the leftmost node of each level. To get the left view of a binary tree, we can use a recursive approach. We keep track of the current level and only add the first node we encounter at that level to the result.

var leftSideView = function(root) {
  if(!root) return [];
  let queue = [root];
  let result = [];
  while(queue.length) {
    let length = queue.length;
    for(let i = 0; i < length; i++) {
      let currentNode = queue.shift()
      if(i === 0) result.push(currentNode.val);
      if(currentNode.left) queue.push(currentNode.left);
      if(currentNode.right) queue.push(currentNode.right);
    }
  }
  return result
};

• Right View: In the right view of a binary tree, we see the rightmost node of each level. To get the right view of a binary tree, we can also use a recursive approach. We keep track of the current level and only add the last node we encounter at that level to the result.

var rightSideView = function(root) {
  if(!root) return [];
  let queue = [root];
  let result = []; 
  while(queue.length) {
    let length = queue.length;
    for(let i = 0; i < length; i++) {
      let currentNode = queue.shift()
      if(i === length - 1) result.push(currentNode.val);
      if(currentNode.left) queue.push(currentNode.left);
      if(currentNode.right) queue.push(currentNode.right);
    }
  }
  return result;
};

• Top View: In the top view of a binary tree, we see the nodes that are visible from the top. We can visualize the top view of a binary tree as if we are looking at the tree from the top. To get the top view of a binary tree, we can use a map to store the horizontal distance of each node from the root node. We perform a level order traversal of the binary tree and add the first node we encounter at a horizontal distance to the result.

var topView = function(root){
  let a = [],b = [];
  if (root == null) {
    return [];
  }
  let root2 = root;
  while (root != null) {
    a.push(root.data);
    root = root.left;
  }
  while (root2 != null) {
    b.push(root2.data);
    root2 = root2.right;
  }
  if (b.length > 0) {
    b.shift();
  }
  let ans = a.concat(b);
  return ans;
}

• Bottom View: In the bottom view of a binary tree, we see the nodes that are visible from the bottom. To get the bottom view of a binary tree, we can use a map to store the horizontal distance of each node from the root node. We perform a level order traversal of the binary tree and update the map with the latest node we encounter at a particular horizontal distance. The final map will contain the nodes that are visible from the bottom.

var bottomView = function(root) {
  if(root === null) return [];
  let ans = [];
  let map = new Map();
  let queue = [[root, 0]];
  while(queue.length) {
    let [node, line] = queue.shift();
    map.set(line, node.val);
    if(node.left) queue.push([node.left, line - 1]);
    if(node.right) queue.push([node.right, line + 1])
  }
  for(let value of map.values()) {
    ans.push(value);
  }
  return ans;
};

Outro💚

In this blog, we discussed the basics of binary trees and some different views of binary trees. Binary trees are a powerful data structure that can be used to solve many problems. Different views of binary trees provide us with different perspectives and help us understand the structure and organization of binary trees better.

If you run an organisation and want me to write for you please do connect with me 🙈