Binary Search Tree Typo - Microsoft Top Interview Questions


Problem Statement :


You are given a binary tree root which is almost a binary search tree except two nodes' values have been swapped. Return the original binary search tree.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [2, [5, null, null], [7, [1, null, null], [8, null, null]]]

Output

[2, [1, null, null], [7, [5, null, null], [8, null, null]]]

Explanation

We can swap 1 and 5.




Example 2

Input




root = [0, [1, null, null], null]

Output



[1, [0, null, null], null]

Explanation

We can swap 0 and 1.



Solution :



title-img




                        Solution in C++ :

void check(Tree* root, Tree*& prev, Tree*& node1, Tree*& node2) {
    if (!root) return;
    check(root->left, prev, node1, node2);
    if (prev && prev->val >= root->val) {
        if (node1 == nullptr) node1 = prev;
        node2 = root;
    }
    prev = root;
    check(root->right, prev, node1, node2);
}

Tree* solve(Tree* root) {
    Tree *node1 = nullptr, *node2 = nullptr, *prev = nullptr;
    check(root, prev, node1, node2);
    swap(node1->val, node2->val);
    return root;
}
                    


                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public Tree solve(Tree root) {
        List<Tree> values = new ArrayList<>();
        inOrder(root, values);
        findAndSwap(values);
        return root;
    }

    private void inOrder(Tree node, List<Tree> values) {
        if (node == null)
            return;

        inOrder(node.left, values);
        values.add(node);
        inOrder(node.right, values);
    }

    private void findAndSwap(List<Tree> values) {
        Tree first = null;
        Tree second = null;

        for (int i = 1; i < values.size(); i++) {
            if (values.get(i - 1).val > values.get(i).val) {
                if (first == null) {
                    first = values.get(i - 1);
                    second = values.get(i);
                } else {
                    second = values.get(i);
                }
            }
        }

        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        left = right = None
        last_node = Tree(-float("inf"))

        for node in self.morris_inorder(root):
            if node.val < last_node.val:
                left = left or last_node
                right = node
            last_node = node

        left.val, right.val = right.val, left.val

        return root

    @staticmethod
    def morris_inorder(node):
        temp = None
        while node:
            if node.left:
                temp = node.left
                while temp.right and temp.right != node:
                    temp = temp.right
                if temp.right:
                    temp.right = None
                    yield node
                    node = node.right
                else:
                    temp.right = node
                    node = node.left
            else:
                yield node
                node = node.right
                    


View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →