Tricks to compute the time and space complexities. Part-2 (Binary Tree)
Learn the tips and tricks to find the time and space complexities of Binary tree algorithms:
Difference between nodes of alternate vertical levels in a tree
The question below is given in the format in which questions are asked on coding interview Platforms like HackerRank, CodeChef, CodeJam, etc. PROBLEM STATEMENT Vertical level of a node is the vertical distance of that node from the root. Vertical level of the root node is 0. If a node is at vertical level k, […]
Water overflowing from glass arranged in form of triangle
Glasses are arranged in the form of triangle (on top of each other) as shown below: 1 2 3 4 5 6 7 8 9 10 ……………….. …………………. Liquid is poured into 1st glass (Glass no. 1). When it is full, then extra liquid will flow into the glasses 2 and 3 in equal quantities. […]
Sum of all the nodes in a tree
Given a binary tree, where each node is having an integer value. Write a function that accept the root of this tree and returns the sum of all the nodes in the tree. The sum of all the nodes in the
Iterative pre-order traversal using stack
We have seen the in-order traversal of a binary tree. It is a recursive code. Recursion stack can be simulated using an explicit Stack data structure and keeping the function non-recursive. Let us see how:
Right view of a binary tree
Write code to print the right-view of a binary tree. Right-view of the tree is the nodes visible when the tree is seen from the right side. If there are two nodes at the same level, then only the right-most node will be visible in the right-view as shown below:
Left view of a binary tree
Write code to print the left-view of a binary tree. Left-view of the tree is the nodes visible when the tree is seen from the left side. If there are two nodes at the same level, then only the left-most node will be visible in the left-view as shown below:
Check if a Tree is Almost Complete Binary Tree
Given a pointer to the root node of the tree, write code to find if it is an Almost Complete Binary Tree or not? A Binary Tree of depth d is Almost Complete iff: The tree is Complete Binary Tree (All nodes) till level (d-1). At level d, (i.e the last level), if a Node […]
Check if two node are siblings in a binary tree
Given a binary tree and two values. Find if these values appear in sibling nodes in the tree. For example, if tree is Then 2 and 6 are siblings but 6 and 9 are not siblings (they are cousin nodes).
Convert a Binary Tree to a Doubly Linked List
The structure of Node of a Binary Tree and Doubly linked list are same. struct Node { int data; Node* left; Node* right; } Structure of Node of a Binary Tree struct Node { int data; Node* previous; Node* next; } Structure of Node of a Doubly linked list If we treat […]
