Code_Challenges/Day 175.java at main · MrAtharvaB/Code_Challenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public ArrayList<Node> findPreSuc(Node root, int key) {
        Node pre = null, suc = null;
        Node curr = root;

        while (curr != null) {
            if (curr.data < key) {
                pre = curr;
                curr = curr.right;
            } else if (curr.data > key) {
                suc = curr;
                curr = curr.left;
            } else {
                if (curr.left != null) {
                    Node temp = curr.left;
                    while (temp.right != null) {
                        temp = temp.right;
                    }
                    pre = temp;
                }

                if (curr.right != null) {
                    Node temp = curr.right;
                    while (temp.left != null) {
                        temp = temp.left;
                    }
                    suc = temp;
                }

                break;
            }
        }

        ArrayList<Node> res = new ArrayList<>();
        res.add(pre);
        res.add(suc);

        return res;
    }
}