Programming/pair bst using stack.cpp at master · arshdeep/Programming · 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <stack>
using namespace std;

struct node
{
    int val;
    struct node *left, *right;
};

struct node * NewNode(int val)
{
    struct node *tmp = (struct node *)malloc(sizeof(struct node));
    tmp->val = val;
    tmp->right = tmp->left =NULL;
    return tmp;
}

bool isPairPresent(node *root, int x)
{
	stack<node *> fstk;
	stack<node *> rstk;
	bool flag1 = true, flag2 = true;
	node *cur = root;
	node *cur2 = root;

	int val1 = 0, val2 = 0;
	while (1)
	{
		while (flag1)
		{
			if (cur)
			{
				fstk.push(cur);
				cur = cur->left;
			}
			else if (fstk.empty()) {
				flag1 = false;
			}
			else {
				node *top = fstk.top();
				val1 = top->val;
				fstk.pop();
				cur = top->right;
				flag1 = false;
			}
		}

		while (flag2)
		{
			if (cur2)
			{
				rstk.push(cur2);
				cur2 = cur2->right;
			}
			else if (rstk.empty()) {
				flag2 = false;
			}
			else {
				node *top = rstk.top();
				val2 = top->val;
				rstk.pop();
				cur2 = top->left;
				flag2 = false;
			}
		}

		if (val1 + val2 == x) {
			cout<< "found";
			return true;
		}

		if (val1 + val2 > x)
			flag2 = true;
		else
			flag1 = true;

		if (val1 >= val2)
			return false;
	}
}
int main()
{
    /*
                   15
                /     \
              10      20
             / \     /  \
            8  12   16  25    */
    struct node *root =  NewNode(15);
    root->left = NewNode(10);
    root->right = NewNode(20);
    root->left->left = NewNode(8);
    root->left->right = NewNode(12);
    root->right->left = NewNode(16);
    root->right->right = NewNode(25);

    int target = 33;
    if (isPairPresent(root, target) == false)
        printf("\n No such values are found\n");

    getchar();
    return 0;
}