Ace your Coding Interview
Get hired by top tech companies with our comprehensive interview preparation.
Get StartedGiven 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.
Write an efficient algorithm to find postorder traversal on a given binary tree from its inorder and preorder sequence.
Given a binary tree, write an iterative algorithm to print the leaf-to-root path for every leaf node. Use of recursion is prohibited.
Given a binary tree, write an efficient algorithm to compute the maximum number of nodes in any level in the binary tree.
Given an array representing a binary tree, such that the parent-child relationship is defined by (A[i], i) for every index i in array A, build a binary tree out of it. The root node’s value is i if -1 is present at index i in the array.
Given a binary tree, write a recursive algorithm to print all paths from leaf to root node.
Given a binary tree, write an efficient algorithm to invert it.
Given a normal binary tree, convert it into a Left–child right–sibling (LC–RS) binary tree. Each node in the LC–RS binary tree has two pointers: one to the node’s left child and one to its next sibling in the original binary tree.
Write an efficient algorithm to print the two-dimensional view of a binary tree.
Given an N × N ancestor matrix, whose cell (i, j) has the value true if i is the ancestor of j in a binary tree, construct a binary tree from it where binary tree nodes are labeled from 0 to N-1.
Write an algorithm to compute a binary tree’s height with leaf nodes forming a circular doubly linked list where the leaf node’s left and right pointers will act as a previous and next pointer of the circular doubly linked list, respectively.
Huffman coding (also known as Huffman Encoding) is an algorithm for doing data compression, and it forms the basic idea behind file compression. This post talks about the fixed-length and variable-length encoding, uniquely decodable codes, prefix rules, and Huffman Tree construction.