Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
Category Archives: binary tree
Lowest Common Ancestor of a Binary Tree Part I
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
Lowest Common Ancestor of a Binary Search Tree (BST)
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
Construct Binary Tree From Inorder and Preorder/Postorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Convert Binary Search Tree (BST) to Sorted Doubly-Linked List
Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.
Convert Sorted List to Balanced Binary Search Tree (BST)
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Convert Sorted Array to Balanced Binary Search Tree (BST)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Largest Binary Search Tree (BST) in a Binary Tree
Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.
Largest Subtree Which is a Binary Search Tree (BST)
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Binary Tree Post-Order Traversal Iterative Solution
Given a binary tree, print the elements in post-order iteratively without using recursion.
Print Edge Nodes (Boundary) of a Binary Tree
Print all edge nodes of a complete binary tree anti-clockwise. That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes. In other words, print the boundary of the tree. Variant: Print the same for a tree that is not complete.
Serialization/Deserialization of a Binary Tree
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.
Saving a Binary Search Tree to a File
Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.
How to Pretty Print a Binary Tree
Have you ever thought of pretty-printing a binary tree?
Printing a Binary Tree in Zig Zag Level-Order
Given a binary tree, print out the tree in zig zag level order (ie, from left to right, then right to left for the next level and alternate between). Output a newline after the end of each level.
Binary Tree Level-Order Traversal Using Depth First Search (DFS)
Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed.
Printing a Binary Tree in Level Order
Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level.
Determine if a Binary Tree is a Binary Search Tree (BST)
Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.
Maximum Height (Depth) of a Binary Tree
Given a binary tree, find its maximum height.
A binary tree problem – Populating next right pointers in each node
Given a binary tree
|
1 2 3 4 5 |
struct Node { Node* leftChild; Node* rightChild; Node* nextRight; } |
Populate the nextRight pointers in each node.