Given a BST with 2 nodes swapped, fix it

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/recover-binary-search-tree-problem/. Problem Given a BST with 2 nodes swapped fix it. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8 and 20, and BST is changed. Input Tree: 10 / \ 5 8 / \ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree....

Read More

Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/given-a-binary-search-tree-with-2-nodes-swapped-find-number-of-pairs-not-following-bst-properties/. Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post. Example Consider the BST: Following is the correct BST 10 / \ 5 20 / \ 2 8 Now we swap  8...

Read More

For a Given node of a binary tree, print the K distance nodes.

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/all-nodes-distance-k-in-binary-tree/. Problem You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted...

Read More

Print all nodes that are at distance k from a leaf node

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/nodes-at-distance-k-from-leaf-nodes-in-binary-tree/. Problem Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For...

Read More

Find the distance between 2 nodes in Binary Tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/distance-between-two-nodes-in-binary-tree/. Problem Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Example Dist(-4,3) = 2, Dist (-4,19) = 4 Dist(21,-4) =...

Read More

Program to count leaf nodes in a binary tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/problems/count-number-of-leaf-nodes-in-binary-tree/. Problem Count leaf nodes in a binary tree Solution Method 1 - Recursive Here is the logic: If node is NULL then return 0. Else If left and right child nodes are NULL return 1. Else recursively calculate leaf count of the tree using below formula.Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree Here is the recursive solution: int...

Read More