Print right view of a binary tree
Given a binary tree, write an efficient algorithm to print its right view. For example, the right view of a given binary tree is 1, 3, 6, 8.
Tag: Depth-first search
Construct an ancestor matrix from a binary tree
Given a binary tree whose nodes are labeled from 0 to N-1, construct an N × N ancestor matrix. An ancestor matrix is a boolean matrix, whose cell (i, j) is true if i is an ancestor of j in the binary tree.
Construct a height-balanced BST from a sorted doubly linked list
Given a sorted doubly linked list, in-place convert it into a height-balanced Binary Search Tree (BST). The difference between the height of the left and right subtree for every node of a height-balanced BST is never greater than 1.
Find postorder traversal of a binary tree from its inorder and preorder sequence
Write an efficient algorithm to find postorder traversal on a given binary tree from its inorder and preorder sequence.
Remove nodes from a BST that have keys outside a valid range
Given a BST and a valid range of keys, remove nodes from BST that have keys outside the valid range.
Traverse a given directory using BFS and DFS in Java
This post will discuss how to traverse the given directory and list out all files present in it and all its sub-directories using BFS and DFS.
Iteratively print the leaf to root path for every leaf node in a binary tree
Given a binary tree, write an iterative algorithm to print the leaf-to-root path for every leaf node. Use of recursion is prohibited.
Find a pair with the given sum in a BST
Given a binary search tree, find a pair with a given sum present in it.
Find the cost of the shortest path in DAG using one pass of Bellman–Ford
Given a directed acyclic graph (DAG) and a source vertex, find the shortest path’s cost from the source vertex to all other vertices present in the graph. If the vertex can’t be reached from the given source vertex, print its distance as infinity.
Compute the maximum number of nodes at any level in a binary tree
Given a binary tree, write an efficient algorithm to compute the maximum number of nodes in any level in the binary tree.
Print all paths from leaf to root node of a binary tree
Given a binary tree, write a recursive algorithm to print all paths from leaf to root node.
Invert Binary Tree – Iterative and Recursive Solution
Given a binary tree, write an efficient algorithm to invert it.