Tree

1.Tree Definition

//Tree Declaration
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){};
    TreeNode(int x):val(x),left(nullptr),right(nullptr){};
    TreeNode(int x, TreeNode* l,TreeNode* r):val(x),left(l),right(r){};
};
//Tree Initializaiton with default value zero
TreeNode *root = new TreeNode(0, nullptr, nullptr);

2.Binary Search Tree

2.1 Binary Search Tree Definition

Binary Search Tree is a node-based binary tree data structure which has following structures:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys larger than the node’s key.
The left and right subtree each must also be a binary search tree.

BST Traversal

Inorder Traversal

BFS Solution:

BSTIterator(TreeNode* root) {
        //create queue to store all node value in inorder sequence
        queue<int> q;
        if(!root)return;
        stack<TreeNode*> s;
        s.push(root);

        TreeNode *node=s.top()->left;
        while(!s.empty()||node){

            while(node){
                s.push(node);
                node=node->left;
            }
            q.push(s.top()->val);

            if(s.top()->right){
                node=s.top->right;
            }
            s.pop();
        }
}

173 binary search tree iterator(BFS)(stack/queue)
230 Kth Smallest Element in a BST(BFS/DFS)(Q:A)
98 Validate Binary Search Tree(Q:A)(BFS inorder traversal, DFS by setting lower and upper limit)
333 Largest BST Subtree(Q:A)(DFS by setting lower and upper limit)

Try to understand the difference how to set lower/upper limit between issue 98 and issue 333

285 Inorder Successor in BST(Q:A)(BFS,stack)

Note that when comparing integer type value with long type value, an object of type int is always converted to the type long because type long has higher rank than type int.

337 House Robber III(Q:A) Note that intuitive approach would be to use boolean variable to check if current node is robbed or not, but it will create redundant calculations, improvement would be to return robbed value and not robbed value at the same time.

298 Binary Tree Longest Consecutive Sequence(Q:A)(DFS Traversal)

Note that if dfs traversal needs to compare output of everynodes while everynodes need to traverse to get its output value, then set output value of every tree node as return value, temporarily compared result as input and pass by reference.

Preorder Traversal(root->left->right)

199 Binary Tree Right Side View(Q:A)(BFS)(DFS->preorder traversal)
255 Verify Preorder Sequence in Binary Search Tree(Q:A)
314 Binary Tree Vertical Order Traversal(Q:A)
Think about data structure to store nodes value.

331 Verify Preorder Serialization of a Binary Tree(Q:A)

Postorder Traversal(left->right->root)

Validate BST

98 Validate Binary Search Tree(Q:A)(BFS inorder traversal, DFS by setting lower and upper limit)
255 Verify Preorder Sequence in Binary Search Tree(Q:A)

Non-BST Traversal

364 Nested List Weight Sum II(Q:A)

Note that when reversely assigning or returning depth of nested list, using hash table as global variable to store value then loop through.

Binary Tree Basic Operation

Leaves

366 Find Leaves of Binary Tree(Q:A)(returning height to return leaves)

Sum

Height

Nodes

Count Complete Tree Nodes(Q:A)(DFS, Binary Search)

BST Ancestor

236 Lowest Common Ancestor of a Binary Tree(Q:A)
235 Lowest Common Ancestor of a Binary Search Tree(Q:A)

Note that if task is to need to traverse all nodes of binary tree meanwhile see if any nodes could fulfill requirements of tasks, then adding a new private result value and return state of every nodes during DFS.

2.3 Binary Search Tree Construction:

96 Unique Binary Search Trees (Q:A)(DFS)
95 Unique Binary Search Tree_II (Q:A)(DP)
106 Construct Binary Tree from Inorder and PostOrder Traversal(Q:A)

Ust two pointers to track range of inorder of current node, one or two pointer/index to track root of postorder of current node, note that traverse post order from right to left.

Construct List to BST

109 Convert Sorted List to Binary Search Tree(Q:A)

List->Array->DFS using boundary->Tree

2.4 Path

113 Path Sum II(Q:A)(DFS)

2.5 Modify Tree Data Structure

2.5.1 Flatten Binary Tree(DFS):

114 Flatten Binary Tree to Linked List(Q:A)

Since every depth search we need tail of left subtree to be connected to top of right subtree, return tail of every flatten root is necessary.

Don’t forget to set root left tree to be nullptr.

2.5.2 Next Pointer

116 Populating Next Right Pointers in Each Node(Q:A)

We need to build ‘next’ connection between four tree nodes from their two root tree nodes.

Given dicussion above, dfs function would be like:

    void func(TreeNode* left, TreeNode *right){}

117 Populating Next Right Pointers in Each Node II(Q:A)

Note that better solution would be breadth first search since it’s not perfect binary tree.