Need help on Binary tree procedures (NOT binary search tree)

Question

I'm trying to implement a binary tree (NOT a binary search tree). It'll be mostly a class template consisting of insert/delete/search & clear procedures. The data held in the nodes could be anything. Something like below :

template<class T>
class BinaryTree
{
public:
    BinaryTree(int size);
    ~BinaryTree();
    virtual bool insert(T data);
    virtual bool remove(T data);
    virtual void clear();
    virtual bool search(T data);
    virtual void display(std::string str, ETravType type);
    virtual unsigned int getSize();
    //friend void swapWithLastNode(Node *root, Node **nodeToRemove);
protected:
    virtual void inorder(Node<T>* root);
    virtual void preorder(Node<T>* root);
    virtual void postorder(Node<T>* root);
    virtual void removeAll(Node<T>* root);
    Node<T>* root;
    int max;
    unsigned int curSize;
};

I need some help on the algorithms, preferably iterative (want to avoid recursive due to stack size restrictions), to use for insert, search & delete:

Insert: How to ensure that the tree doesn't get left/right skewed ?
Delete: What is the best way to go about deletion when the node has both the children (For ex: In BST, you replace with inorder successor).
Search: Is there any efficient way so as to prevent a O(n) search ?

There's an abundance of resources on the web for BST procedures (mostly recursive), but none for Binary Tree (or atleast I was not able to find anything). Hence thought of posting it here.

Your questions about insert and delete seem to indicate to me that you don't care about the positions of the nodes in the tree and at that point I need to ask why are you even using a binary tree instead of just a singly-linked list? — PeterT

Saurav Sahu Saurav Sahu · Accepted Answer · 2016-11-02T07:44:08

There is a genuine reason to favour BST over BT.

BST is log(N) for insertion, deletion and search, while BT may end up with complete traversal of tree at the cost of O(N).

Insert: How to ensure that the tree doesn't get left/right skewed ?

I am afraid that would not make any difference to the overall performance of the tree. If you still want to do that, learn about self-balancing tree.
Delete: What is the best way to go about deletion when the node has both the children (For ex: In BST, you replace with inorder successor).

For deletion, just pick any leaf node of the tree and substitute it at that position. Binary tree has no pattern, so picking random node would not make any sort of difference. So, no problem in picking up leaf node.
Search: Is there any efficient way so as to prevent a O(n) search ?

No, there is no better way to prevent O(n) search. You need to traverse the complete tree, there is no pattern/order of nodes in BT to help you navigate efficiently.

Need help on Binary tree procedures (NOT binary search tree)

1 Answers