Member Avatar for anjutalks

Hello,
i really need code for creating a binary search tree from pre-order and post order traversals.......and print its output in post order and level order traversals....pls help...

  • 3 Contributors
  • 2 Replies
  • 83 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by Member #46692

Dani AI

Generated

asked for building a binary search tree from traversals and then printing postorder and level order. Quick clarification first: for a BST with unique keys a single preorder (or single postorder) sequence determines the tree uniquely. For a general binary tree, preorder+postorder together still may be ambiguous unless extra constraints are given.

As suggested, standard algorithms are the place to start, and pointed to practical examples. A compact, robust approach is an O(n) recursive builder that walks the traversal with an index and enforces min/max bounds. For preorder it consumes left-to-right; for postorder it consumes right-to-left and constructs the right subtree before the left. The code below shows both builders plus functions to print postorder and level order.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Node {
    int val; Node* left; Node* right;
    Node(int v): val(v), left(nullptr), right(nullptr) {}
};

Node* buildPre(const vector<int>& pre, int& i, long long low, long long high) {
    if (i >= (int)pre.size()) return nullptr;
    int v = pre[i];
    if (v <= low || v >= high) return nullptr;
    Node* root = new Node(v); ++i;
    root->left  = buildPre(pre, i, low, v);
    root->right = buildPre(pre, i, v, high);
    return root;
}

Node* bstFromPreorder(const vector<int>& pre) {
    int i = 0; return buildPre(pre, i, LLONG_MIN, LLONG_MAX);
}

Node* buildPost(const vector<int>& post, int& i, long long low, long long high) {
    if (i < 0) return nullptr;
    int v = post[i];
    if (v <= low || v >= high) return nullptr;
    Node* root = new Node(v); --i;
    root->right = buildPost(post, i, v, high);
    root->left  = buildPost(post, i, low, v);
    return root;
}

Node* bstFromPostorder(const vector<int>& post) {
    int i = (int)post.size() - 1; return buildPost(post, i, LLONG_MIN, LLONG_MAX);
}

void printPost(Node* r) {
    if (!r) return;
    printPost(r->left); printPost(r->right);
    cout << r->val << ' ';
}

void printLevel(Node* r) {
    if (!r) return;
    queue<Node*> q; q.push(r);
    while (!q.empty()) {
        Node* n = q.front(); q.pop();
        cout << n->val << ' ';
        if (n->left) q.push(n->left);
        if (n->right) q.push(n->right);
    }
}

Notes: if duplicates exist, decide a consistent tie rule (e.g., duplicates go left) and change the comparison logic accordingly. To validate input pairs (pre/post), reconstruct from one sequence and compare the other traversal produced by that tree; if they differ the inputs are inconsistent. For very deep trees prefer an iterative/stack variant or increase recursion limits.

Recommended Answers

All 2 Replies

Member Avatar for Dave Sinkula

Hello,
i really need code for creating a binary search tree from pre-order and post order traversals.......and print its output in post order and level order traversals....pls help...

Your best bet is to do your own homework, read your own textbook, etc. But if you insist on doubling your effort, start here.

Member Avatar for Member #46692

Assuming you have the requisite infrastructure in place for insertion etc have a look here for ideas.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.