-
Notifications
You must be signed in to change notification settings - Fork 0
/
find_nextNode.cpp
43 lines (34 loc) · 1.08 KB
/
find_nextNode.cpp
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
#include <iostream>
struct BinaryTreeNode {
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode* parent;
};
class findNextNode {
public:
BinaryTreeNode* getNext(BinaryTreeNode* input) {
// deal with the null input
if (input == nullptr)
return nullptr;
BinaryTreeNode* pNext;
// deal with the case where there is right subtree
if (input->m_pRight != nullptr) {
BinaryTreeNode* pRight = input->m_pRight;
while (pRight->m_pLeft != nullptr) {
pRight = pRight->m_pLeft;
}
pNext = pRight;
} else if (input->parent != nullptr) {
BinaryTreeNode* pCurrent = input;
BinaryTreeNode* pParent = input->parent;
while (pParent != nullptr && pCurrent == pParent->m_pRight) {
pCurrent = pParent;
pParent = pParent->parent;
}
pNext = pParent;
}
return pNext;
// deal witht the case where there is no
}
};