Find k’th largest node in a BST
Given a BST and a positive number k, find the k’th largest node in the BST.
Tag: Depth-first search
Find the diagonal sum of a binary tree
Given a binary tree, calculate the sum of all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes a 45–degree angle with the parent.
Determine whether a given binary tree is a BST or not
Given a binary tree, determine if it is a BST or not. This problem has a simple recursive solution. The BST property is the key to figuring out whether a tree is a BST or not.
Find maximum sum root to leaf path in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum sum root-to-leaf path, i.e., the maximum sum path from the root node to any leaf node in it.
Truncate a binary tree to remove nodes that lie on a path having a sum less than `k`
Given a binary tree and a number k, remove nodes from the tree which lie on a complete path having a sum less than k.
Convert a binary tree to a full tree by removing half nodes
Given a binary tree, convert it into a full tree by removing half nodes (remove nodes having one child).
Sink nodes containing zero to the bottom of a binary tree
Given a binary tree containing many zero nodes, sink nodes having zero value at the bottom of the subtree rooted at that node. In other words, the output binary tree should not contain any node having zero value that is the parent of the node having a non-zero value.
In-place convert a binary tree to a doubly-linked list
Given a binary tree, in-place convert it into a doubly linked list. The left and right pointers of binary tree nodes should act as previous and next pointers in a doubly-linked list, and the doubly linked list nodes should follow the same order of nodes as inorder traversal on the tree.
Print diagonal traversal of a binary tree
Given a binary tree, print all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes a 45–degree angle with the parent.
Perform vertical traversal of a binary tree
Given a binary tree, perform vertical traversal on it. In vertical traversal, nodes of a binary tree are printed in vertical order. Assume that the left and right child makes a 45–degree angle with the parent.
Find the vertical sum of a binary tree
Given a binary tree, the print vertical sum of it. Assume the left and right child of a node makes a 45–degree angle with the parent.
Find ancestors of a given node in a binary tree
Given a binary tree, find all ancestors of a given node in it.