inorder traversal

Jun 13, 2022 at 8:33am
Pen72 (74)
Hi I'm trying to implement inorder traversal in BST.
The issue I got here is, if the data is already in BST, the operation must be ignored. I used a vector to record whether the data is in the BST or not, but it still prints out the repeat number.

Input Format

The input contains only one test case. The first line contains an integer n, which means how many data will be inserted to Binary Search Tree.

Each of the next n lines contains one integer, which represents the data inserted to the BST.

Output Format

Print the result of the inorder traversal. After printing an integer, a newline should be printed immediately.

Sample Input 0

4
2
3
2
1
Sample Output 0

1
2
3


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
 
  #include <iostream>
#include <vector>
 #include <algorithm>
#include <unordered_map>
using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
};
 
node* newNode(int data)
{
    node* temp = new node();
 
    temp->data = data;
    temp->left = temp->right = NULL;
 
    return temp;
}

node* constructTreeUtil(vector<int> pre, int* preIndex, int low,
                        int high, int size)
{

    if (*preIndex >= size || low > high)
        return NULL;
 
    node* root = newNode(pre[*preIndex]);
    *preIndex = *preIndex + 1;
 
    if (low == high)
        return root;
 
    int i;
    for (i = low; i <= high; ++i)
        if (pre[i] > root->data)
            break;

    root->left = constructTreeUtil(pre, preIndex, *preIndex,
                                   i - 1, size);
    root->right
        = constructTreeUtil(pre, preIndex, i, high, size);
 
    return root;
}

node* constructTree(vector<int> pre, int size)
{
    int preIndex = 0;
    return constructTreeUtil(pre, &preIndex, 0, size - 1,
                             size);
}
 

void printInorder(node* node)
{
    if (node == NULL)
    return;
    printInorder(node->left);
    vector<uint64_t> tree;
    tree.clear();
     auto it = std::find(tree.begin(), tree.end(), node->data);
     if (it == tree.end())
    {
         cout << node->data << "\n";
         tree.push_back(node->data);
        
    }
    printInorder(node->right);
}



int main()
{
    int n;
    cin>>n;
    vector<int> A(n);
       for(auto &a:A) cin>>a;
    node* root = constructTree(A,n);
    printInorder(root);
    cout<<"\n";
    return 0;
}
Edit & run on cpp.sh
Jun 13, 2022 at 9:08am
seeplus (6627)
To create a BST with no duplicates and to traverse in-order then consider:

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
 
#include <iostream>

class node {
public:
	int data {};
	node* left {};
	node* right {};

	node(int d) : data(d) {}
};

using Tree = node*;

bool add(Tree& t, int n) {
	if (!t)
		return t = new node(n);

	if (t->data != n)
		return add(t->data < n ? t->right : t->left, n);

	return false;
}

void preorder(const Tree t) {
	if (t) {
		preorder(t->left);
		std::cout << t->data << '\n';
		preorder(t->right);
	}
}

int main() {
	size_t n {};

	std::cin >> n;

	Tree t {};

	for (size_t i {}; i < n; ++i) {
		int d {};

		std::cin >> d;
		add(t, d);
	}

	std::cout << '\n';
	preorder(t);
}
Edit & run on cpp.sh



4
2
3
2
1

1
2
3

Last edited on Jun 13, 2022 at 12:28pm
Jun 13, 2022 at 11:01am
lastchance (6980)
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
 
#include <iostream>
using namespace std;

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

void insert( node *&n, int value )
{
   if      (       !n        ) n = new node{ value, 0, 0 };
   else if ( value < n->data ) insert( n->left , value );
   else if ( value > n->data ) insert( n->right, value );
}

void output( node *n )
{
   if ( !n ) return;
   output( n->left );
   cout << n->data << '\n';
   output( n->right );
}

int main()
{
   node *root = nullptr;
   int n;
   cin >> n;
   while ( n-- )
   {
      int value;
      cin >> value;
      insert( root, value );
   }
   output( root );
}
Edit & run on cpp.sh
Jun 13, 2022 at 1:15pm
ElusiveTau (173)
Your question asks about Inorder traversal but your post alludes to tree insertion. Do you know if your tree creation code is correct? Are you asking about node insertion or traversal?

The issue I got here is, if the data is already in BST, the operation must be ignored

Dealing with duplicate nodes isn't a concern of tree traversal. It is when you insert a node.



Topic archived. No new replies allowed.