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.
Category: Tree
Invert Binary Tree – Iterative and Recursive Solution
Given a binary tree, write an efficient algorithm to invert it.
Find k’th smallest node in a BST
Given a BST and a positive number k, find the k’th smallest node in it.
Convert a binary tree to BST by maintaining its original structure
Convert a given binary tree into a BST (Binary Search Tree) by keeping its original structure intact.
Convert binary tree to Left-child right-sibling binary tree
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.
Print a two-dimensional view of a binary tree
Write an efficient algorithm to print the two-dimensional view of a binary tree.
Construct a binary tree from an ancestor matrix
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.
Calculate the height of a binary tree with leaf nodes forming a circular doubly linked list
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.
Replace every array element with the least greater element on its right
Write an efficient algorithm to replace every element of a given array with the least greater element on its right or with -1 if there are no greater elements.
Huffman Coding Compression Algorithm
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.
Check if a binary tree is height-balanced or not
Given a binary tree, write an efficient algorithm to check if a tree is height-balanced or not. In a height-balanced tree, the absolute difference between the height of the left and right subtree for every node is 0 or 1.
Java Implementation of Trie Data Structure
Trie is a tree-based data structure used for efficient retrieval of a key in a huge word set. In this post, we will implement the Trie data structure in Java.