Tree Operation

BST traversal

In order:

left -> root -> right

std::stack<Node*> stk;
Node cur; // current node

Tree<T>::Iterator::Iterator(Tree::Node *root) {
    while (root) {
        stk_.push(root);
        root = root->left_;
    }
    this->operator++();
}

typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
    if (stk_.empty()) {
        curr_ = NULL;
        return *this;
    }
    curr_ = stk_.top();
    stk_.pop();
    Node* next = curr_->right_;
    while (next) {
        stk_.push(next);
        next = next->left_;
    }
    return *this;
}

Pre order:

root -> left -> right

std::stack<Node*> stk;    
Node cur; // current node

Tree<T>::Iterator::Iterator(Tree::Node *root) {
    if (root) {
        cur = root;
        if (root->right) stk.push(root->right);
        if (root->left) stk.push(root->left);
    } else {
        cur = NULL;
    }
}

typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
    if (stk.empty()) {
        cur = NULL;
        return *this;
    }
    cur = stk.top();
    stk.pop();
    if (cur->right) stk.push(cur->right);
    if (cur->left)  stk.push(cur->left);
    return *this;
}

Level order:

traverse through each level

std::queue<Node*> que;    
Node cur; // current node

Tree<T>::Iterator::Iterator(Tree::Node *root) {
    if (root) {
        cur = root;
        if (root->left)  que.push(root->left);
        if (root->right) que.push(root->right);
    } else {
        cur = NULL;
    }
}

typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
    if (que.empty()) {
        cur = NULL;
        return *this;
    }
    cur = que.front();
    que.pop();
    if (cur->left)   que.push(cur->left);
    if (cur->right)  que.push(cur->right);
    return *this;
}

Post order:

left -> right -> root

// Contribute by a Dalao in comment
// Contribute by a Dalao in comment
void Tree::Iterator::find_next_leaf(Node * node) {
    while (node != NULL) {
        stack_.push(node);
        if (node -> left_ != NULL) {
            node = node -> left_;
        } else {
            node = node -> right_;
        }
    }
}

Tree::Iterator::Iterator(Tree::Node * root): curr_(root) {
    if (root == NULL) return;
    find_next_leaf(root);
    curr_ = stack_.top();
    stack_.pop();
}

typename Tree::Iterator & Tree::Iterator::operator++() {
    if (stack_.empty()) {
        curr_ = NULL;
        return *this;
    }
    curr_ = stack_.top();
    stack_.pop();
    if (!stack_.empty()) {
        Node * parent = stack_.top();
        if (curr_ == parent -> left_) {
            find_next_leaf(parent -> right_);
        }
    }
    return *this;
}

AVL

Rotate direction:

/*
case 1 (R) 
    root:  negative unbalanced
    child: negative
case 2 (L) 
    root:  positive unbalanced
    child: positive 
case 3 (LR) 
    root:  negative unbalanced
    child: positive
case 4 (RL) 
    root:  positive unbalanced
    child: negative
*/
TreeNode::RotationType balanceTree(TreeNode * & subroot) {
    if (leftHeavy(subroot)) {
        return leftHeavy(subroot -> left_) ? TreeNode::right : TreeNode::leftRight;
    } else {
        return rightHeavy(subroot -> right_) ? TreeNode::left : TreeNode::rightLeft;
    }
}

Rotate:

// rotate left
void AVLTree < K, V > ::rotateLeft(Node * & t) {
    Node * temp = t -> right;
    t -> right = temp -> left;
    temp -> left = t;
    t -> height = max(heightOrNeg1(t -> left), heightOrNeg1(t -> right)) + 1;
    t = temp;
    t -> height = max(heightOrNeg1(t -> left), heightOrNeg1(t -> right)) + 1;
}

// rotate right
void AVLTree < K, V > ::rotateRight(Node * & t) {
    Node * temp = t -> left;
    t -> left = temp -> right;
    temp -> right = t;
    t -> height = max(heightOrNeg1(t -> left), heightOrNeg1(t -> right)) + 1;
    t = temp;
    t -> height = max(heightOrNeg1(t -> left), heightOrNeg1(t -> right)) + 1;
}

Find unbalanced (deepest):

// apply level order traversal and find deepest unbalanced node
TreeNode * findLastUnbalanced(TreeNode * root) {
    std::queue < TreeNode * > visit;
    visit.push(root);
    TreeNode * result = nullptr;
    while (!visit.empty()) {
        auto front = visit.front();
        visit.pop();
        if (front -> left_) visit.push(front -> left_);
        if (front -> right_) visit.push(front -> right_);
        if (std::abs(getHeight(front -> left_) - getHeight(front -> right_)) > 1) {
            result = front;
        }
    }
    return result;
}