DEV Community

Jiayi Ouyang
Jiayi Ouyang

Posted on

day 13-14|Binary Tree Traversal | leetcode 144,145,94,107,199,637,429,515,116,104, 111,226, 101

#algorithms #datastructures #cpp

[!definition]
Binary Tree is a tree data structure(non-linear) in which each node can have at most two children which are referred to as the left child and right child.
The topmost node is called root, and the bottom-most nodes are called leaves.

Terminology of Binary Tree

  • Root: no incoming edge
  • Child: has incoming edge
  • Sibling: nodes having the same parent are sibling.
  • Degree of a node: number of children of a particular parent. range from 0 to 2
  • Internal/External nodes: leaf nodes are external nodes, non leaf nodes are internal nodes
  • height: number of edges to reach the root. height of root is 0.
  • level: number of nodes to reach the root. level of root is 0.

Types of Binary Tree On the basis of the completion of levels

1. Perfect Binary Tree 满二叉树

[!definition] A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.
Image description
When depth is $k$, there are $2^{k}-1$ nodes

2. Complete Binary Tree 完全二叉树

[!definition] where all the levels are completely filled except possibly the last level and the last level has all keys as left as possible

[!info] ==heap is actual a complete binary tree== with guarantee on the orders between parents and children

[!tip] Perfect Binary Tree vs Complete Binary Tree:
A complete binary tree of height $h$ is a perfect binary tree up to height $h-1$, and in the last level element are stored in left to right order.

3. Balanced Binary Tree

[!definition] A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes.
 For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1.
 Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths is the same and that there are no adjacent red nodes.
 Balanced Binary Search trees are performance-wise good as they provide O(log n) time for search, insert and delete.
Image description

Special Binary Trees

1. ==Binary Search Tree(BST)==

[!Definition] Binary Search Tree has the following properties:

  • the left subtree of a node contains only nodes with keys lesser than the node's key
  • the right subtree of a node contains only nodes with keys greater than the node's key
  • the left and right subtree must also be a binary search tree

2. AVL -- Balanced Search Tree

[!Definition] AVL tree is a self-balancing Binary Search Tree(BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

[!info] C++
map set multimap multiset are all implemented by Balanced Search Tree.
That's why their insertion/deletion's time complexity if $O(logn)$
Remember unordered_map unordered_set are implemented by hash table

Storage of Binary Tree

  1. linked list 
 struct TreeNode
 {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 }
Enter fullscreen mode Exit fullscreen mode
  1. Array say the index of a node is i:
    • the index of its left child is i * 2 + 1
    • the index of its right child is i * 2 + 2

Traversal of Binary Tree

Depth-First Search(DFS)

Can be implemented in both Recursion or Iteration method

  • Preorder Traversal(cur-left-right)
  • Inorder Traversal(left-cur-right)
  • Postorder Traversal(left-right-cur) ### Breadth-First Search(BFS) Can only be implemented by iteration method
  • Level order Traversal

[!Tip]

  1. Stack is a data structure for recursion, so we can write recursion from stack code
  2. BFS is usually done by Queue, since FIFO

How to write recursion

1. Determine the parameters and return type

2. Determine the termination conditions

3. Determine the logic of single-level recursion.

DFS in Recursion

  1. Parameter and return type: the parameters should be a pointer to a node and a reference of a vector that records the results
  2. Termination condition: the passed-in node is nullptr
  3. logic of single-level recursion: keep traversing on children nodes, while insert the cur->val at right order

144 Binary Tree Preorder Traversal 

void traversal(TreeNode* root, vector<int>& vec)
{
    if(root == nullptr) return;
    vec.push_back(root->val);
    traversal(root->left, vec);
    traversal(root->right, vec);    
}


vector<int> preorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

145 Binary Tree Postorder Traversal 

void traversal(TreeNode* root, vector<int> & vec)
{
    if(root == nullptr) return;
    traversal(root->left, vec);
    traversal(root->right, vec);
    vec.push_back(root->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

94 Binary Tree Inorder Traversal 

void traversal(TreeNode* root, vector<int>& vec)
{
    if(root == nullptr) return;
    traversal(root->left, vec);
    vec.push_back(root->val);
    traversal(root->right, vec);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> vec;
    traversal(root, vec);
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

DFS in Iteration

Using Stack, FILO.

Preorder(cur-left-right)

[!important] Preorder does us a huge favor, since we are visiting the middle node first and we output it first, so we only need to push right and left children
we should operate in following order, so that the right child will be out of the stack later than the left:

st.push(root);
while(!st.empty())
{
    cur = st.top(); // get middle
    st.pop();
    vec.push_back(cur->val); // visit middle
    // .. insert cur->val to result
    if(right) push(right);   // right in deeper of stack
    if(left)  push(left);    // left in higher of the stack
}
Enter fullscreen mode Exit fullscreen mode

Inorder(left-cur-right)

[!important] we are visiting middle first but can't output it, we have to push middle nodes in the stack and keep looking for the most left child:

cur = root;
while(cur != nullptr || !st.empty())
{
    if(cur) //push middle and visit left
    {
        st.push(cur); // push every left we find until hit the nullptr
        cur = cur->left;
    }
    else // reach the most left node in a branch
    {
        // pop out its parent, in this situation -- a middle
        // which is also previous left
        cur = st.top();
        st.pop();
        vec.push_back(cur->val); // record result
        cur = cur -> right; // look for the most left in the right branch
    }
}
Enter fullscreen mode Exit fullscreen mode

Postorder(left-right-cur)

[!Tip]
Preorder(cur-left-right)
--reverse left and right--> (cur-right-left) --reverse all-->(left-right-cur)

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();
    // vec.push...
    if(left) st.push(left);
    if(right) st.push(right);
}

reverse(vec...);
Enter fullscreen mode Exit fullscreen mode

Iteration All-in-one

[!Tip] Push the visited but not dealt middle node to the stack and append an extra nullptr as an indicator

Inorder 

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        if(right) st.push(right); // right
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
        if(left) st.push(left);   // left
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}
Enter fullscreen mode Exit fullscreen mode

Preorder 

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        if(right) st.push(right); // right
        if(left) st.push(left);   // left
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}
Enter fullscreen mode Exit fullscreen mode

Postorder 

st.push(root)
while(!st.empty())
{
    cur = st.top();
    st.pop();

    if(cur)
    {
        st.push(cur);             // middle
        st.push(nullptr);             // indicator of undealed middle
        if(right) st.push(right); // right
        if(left) st.push(left);   // left
    }
    else // meet indicator
    {
        cur = st.top(); // get acutual middle
        st.pop();

        vec.push_back(cur->val);
    }
}
Enter fullscreen mode Exit fullscreen mode

BFS -- level order (lc102)

Iteration queue 

vector<vector<int>> levelOrderBy(TreeNode* root) {

    queue<TreeNode*> que;
    vector<vector<int>> vec;
    if(root)    que.push(root);

    // tmp value defines outside of loop for once to avoid duplicated
    // construction and destruction
    int levelSize = 0;
    TreeNode* cur;

    while(!que.empty())
    {
        // at the start of each level, retrieve the size of it
        levelSize = que.size();
        vector<int> levelVec(levelSize);

        // get all the children of current level at left to right order
        for(int i = 0; i < levelSize; ++i)
        {
            cur = que.front();
            que.pop();
            levelVec[i] = cur->val; // record cur val
            if(cur->left)   que.push(cur->left); // push left
            if(cur->right)  que.push(cur->right);// push right
        }

        // append cur level's vals to finnal results
        vec.push_back(levelVec);
    }
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

Recursion 

void traversal(TreeNode* node, vector<vector<int>>& vec, int depth)
{
    if(!node)   return;

    if(depth == vec.size())
    {
        vec.push_back(vector<int>());
    }

    vec[depth].push_back(node->val);

    traversal(node->left, vec, depth + 1);
    traversal(node->right, vec, depth + 1);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> vec;
    traversal(root, vec, 0);
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

107 Binary Tree Level Order Traversal II

BFS + reverse vector at the end
or push each level vector to the front of vec.emplace(vec.begin(), move(levelVec));

199 Binary Tree Right Side View

imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Image description
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

[!info] BFS + only record the most right of each level to the results
To optimize the number of times of finding the most right of each level, we push the children from right to the left, the first of each level 'front()' is the most right one

vector<int> rightSideView(TreeNode* root) {
    queue<TreeNode*> que;
    vector<int> vec;
    if(root)    que.push(root);
    while(!que.empty())
    {
        size_t levelSize = que.size();
        TreeNode* node = que.front();
        // the first of each level is the most right
        vec.emplace_back(node->val);
        while(levelSize-- > 0)
        {
            node = que.front();
            que.pop();
            // each level push right to left
            if(node->right) que.push(node->right);
            if(node->left) que.push(node->left);
        }
    }
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

637. Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

[!info] record sum and number of nodes for each level during recursion, and divide them in the end for calculating average

void traversal(TreeNode* node, vector<pair<double, size_t>>& res, int depth)
{
    if(!node)   return;
    if(depth == res.size())
        res.emplace_back(0, 0);

    res[depth].first += node->val;
    ++res[depth].second;

    traversal(node->left, res, depth + 1);
    traversal(node->right, res, depth + 1);
}

vector<double> averageOfLevels(TreeNode* root) {
    vector<pair<double, size_t>> info;
    traversal(root, info, 0);

    vector<double> res(info.size());
    for(int i = 0; i < info.size(); ++i)
    {
        res[i] = info[i].first / static_cast<double>(info[i].second);
    }
    return res;
}
Enter fullscreen mode Exit fullscreen mode

429 N-ary Tree level Order Traversal

[info] BFS + just replace push left and right to push every valid children

vector<vector<int>> levelOrder(Node* root) {
    queue<Node*> que;
    vector<vector<int>> vec;
    if(root)    que.push(root);
    while(!que.empty())
    {
        size_t size = que.size();
        vector<int> levelVec(size);
        for(size_t i = 0; i < size; ++i)
        {
            Node* node = que.front();
            que.pop();
            levelVec[i] = node->val;
            for(auto& child : node->children)
            {
                if(child)
                    que.push(child);
            }
        }
        vec.emplace_back(move(levelVec));
    }
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

515 Find Largest Value in Each Tree Row 

vector<int> largestValues(TreeNode* root) {
    queue<TreeNode*> que;
    vector<int> vec;
    if(root)    que.push(root);

    while(!que.empty())
    {
        size_t size = que.size();
        int maxValue = INT_MIN;

        for(size_t i = 0; i < size; ++i)
        {
            TreeNode* node = que.front();
            que.pop();
            maxValue = max(maxValue, node->val);
            if(node->left)  que.push(node->left);
            if(node->right)  que.push(node->right);
        }
        vec.emplace_back(maxValue);
    }
    return vec;
}
Enter fullscreen mode Exit fullscreen mode

116 Populating Next Right Pointers in Each Node

[!info] Same question as 117. Populating Next Right Pointers in Each Node II
We don't care if the tree is perfect or not, we are breadth-first-searching anyway.

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
Enter fullscreen mode Exit fullscreen mode

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.

Image description

[!tip] when iterating each level, after retrieving cur and pop it out, the new que->front() is our cur->next

Node* connect(Node* root) {
    queue<Node*> que;
    if(root)    que.push(root);
    while(!que.empty())
    {
        int sz = que.size();
        while(sz-- > 0)
        {
            Node* cur = que.front();
            que.pop();
            if(cur->left)   que.push(cur->left);
            if(cur->right)  que.push(cur->right);

            if(sz == 0)
                cur->next = nullptr;
            else
                cur->next = que.front();
        }
    }

    return root;
}
Enter fullscreen mode Exit fullscreen mode

104 Maximum Depth of Binary Tree

root at depth 1, get the max depth

int maxDepth(TreeNode* root) {
    if(!node)   return 0;
    return max(maxDepth(node->left), maxDepth(node->right)) + 1;
}
Enter fullscreen mode Exit fullscreen mode

111 Minimum Depth of Binary Tree

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children. So when we reach the first leave, return its depth.

Iteration 

int minDepth(TreeNode* root) {
    queue<TreeNode*> que;
    if(root)    que.push(root);
    int depth = 0;
    while(!que.empty())
    {
        ++depth;
        size_t sz = que.size();
        while(sz-- > 0)
        {
            TreeNode* node = que.front();
            que.pop();

            if(!node->left && !node->right) return depth;
            if(node->left) que.push(node->left);
            if(node->right) que.push(node->right);
        }
    }

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Recursion 

int minDepth(TreeNode* root) {
    if(!root)   return 0; // this is a leave

    if(!root->left && root->right) // not leave
        return 1 + minDepth(root->right);

    if(root->left && !root->right)
        return 1 + minDepth(root->left);

    return 1 + min(minDepth(root->left),  minDepth(root->right));  

}
Enter fullscreen mode Exit fullscreen mode

Operations on the BT

226 Invert Binary Tree

Image description

[!caution]
preordered and postordered traversal would both be fine, except the inordered. Since it will invert the left subtree first, then swap it to the right, then invert the right subtree
which leads to original left subtree inverted twice while the original right isn't inverted at all.

However, we can invert the left subtree(original right subtree) again after swap in the inordered traversal LOL.

void traversal(TreeNode* root)
{
    if(!root)   return;
    // preorder
    swap(root->left, root->right);
    traversal(root->left);
    traversal(root->right);

    // postorder
    swap(root->left, root->right);
    traversal(root->left);
    traversal(root->right);

    // inorder
    traversal(root->left);
    swap(root->left, root->right);
    traversal(root->left); // do the trick
}

TreeNode* invertTree(TreeNode* root) {
    traversal(root);
    return root;
}
Enter fullscreen mode Exit fullscreen mode

101 Symmetric Tree

Image description

[!caution] it's not checking every two children of a node as above question, it only compares the left subtree and right subtree of the root.
Plus we are comparing:

  • the outside part: left->left to right->right
  • the inside part: left->right to right->left 
bool compare(TreeNode* left, TreeNode* right)
{
    if(!left && !right)  return true;

    else if((left && !right) || (!left && right) 
            || (left->val != right->val)) 
        return false; 

    return compare(left->left, right->right) 
        && compare(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
    return compare(root->left, root->right);
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Read next

pvsdev profile image

Flax Engine. Exploring game engine & analyzing its source code

Alexandra Kochetkova -

m__mdy__m profile image

Understanding and Implementing Static Arrays

mahdi -

mdarifulhaque profile image

2678. Number of Senior Citizens

MD ARIFUL HAQUE -

madgan95 profile image

Sorting Algorithms (DSA - 4)

Madhav Ganesan -