Basic concept of binary tree

Binary tree is an important type of tree structure. The data structure abstracted from many practical problems is often in the form of binary tree, even the general tree can be simply converted into binary tree, and the memory structure and algorithm of binary tree are relatively simple, so binary tree is particularly important.

The characteristic of binary tree is that each node can only have two subtrees at most, and there are left and right.

For JavaScript, there is no binary tree structure, so you need to create your own binary tree object class to generate the binary tree structure, as shown in the following code:

// The constructor of the binary tree node
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

Copy the code

Each node has val for the current node value, left and right for the left and right nodes, which are new TreeNode types, respectively. A binary tree is made up of several nodes. Where, leaf nodes: also known as terminal nodes, nodes with no subtrees.

Because binary trees in this book are not linear structures, unlike arrays that we can easily represent as linear data structures, for binary trees, in general, in the code, all we can get is an object root, and from the root node we can go through and get the complete binary tree data.

So traversing a binary tree is going through all the nodes of the binary tree according to certain rules and order, so that each node is accessed once, and only once. Because the binary tree is a nonlinear structure, the tree traversal is essentially to transform each node of the binary tree into a linear sequence to represent.

Traverse type

Since each node of the binary tree has different directions, we must specify a traversal order, and different traversal orders will get different results, so it is generally divided into fore-order traversal, in-order traversal, subsequent traversal, and hierarchical traversal.

For fore-order traversal, in-order traversal, and subsequent traversal, the root node is the main one. The root in front represents the pre-order, the root in the middle represents the in-order, and the root in the back represents the follow-up. The left and right nodes are in the order of left and right, so the order of these three traversal modes are:

  • Preorder traversal: access the root node -> traverse the left subtree -> traverse the right subtree
  • Subsequent traversal: traversing the left subtree -> traversing the right subtree -> accessing the root
  • In order traversal: traversing the left subtree -> access the root -> traversing the right subtree

Binary tree as shown below:

  • Preorder traversal result: 0137849256
  • The result of subsequent traversal is 7839415620
  • Sequence traversal result: 7381940526

And sequence traversal is better understood, that is, traversal from top to bottom layer by layer, each layer is traversed from left to right, so the result of binary tree sequence traversal in the figure above is:

  • Sequence traversal result: 0123456789

Code implementation

For the structure of binary tree, because each node of it has two points to new nodes, it is easy to think of using recursion to traverse a binary tree. The idea is as follows:

var loop = function(root){
	// The current node is empty, indicating that the leaf node has been reached
    if (root == null) return
    // Then find the left subtree
    loop(root.left)
    // Then find the right subtree
    loop(root.right)
}
loop(root)
Copy the code

For preorder traversal, in order traversal, and subsequent traversal, it is necessary to access the value of the node at the corresponding position respectively, as follows:

var preorder = []// Preorder result
var inorder = []// Order the result
var postorder = []// Follow the sequence of results

var loop = function(root){
	// The current node is empty, indicating that the leaf node has been reached
    if (root == null) return

    preorder.push(root.val)  / / before order
    loop(root.left)
    inorder.push(root.val)/ / in the sequence
    loop(root.right)
    postorder.push(root.val)/ / after order
}
loop(root)
Copy the code

The recursive method of traversing a binary tree is actually using the depth-first search idea, that is, starting from a node to its left and right nodes, again from the left and right nodes again, until you find the leaf node or the root node.

But for sequence traversal, recursive thinking, it is not very applicable, thought one layer from top to bottom search, it’s more like a breadth-first search, namely from one node to say about all of its nodes, then the all around nodes of each node is the next layer, use this idea, we can use a queue data structure to realize sequence traversal.

A queue is a linear data structure that follows the first-in, first-out rule. In JavaScript, since there is no such data structure as a queue, we can simulate it using an Array.

var queue = [] // Queue (left at the head, right at the end)
queue.push(1)/ / team 1
queue.push(2)/ / the team 2
queue.push(3)/ / the team 3

// now the queue elements are [1,2,3]

queue.shift()1 / / out of the team
queue.shift()2 / / out of the team
Copy the code

The idea of sequence traversal is:

  • The root node joins the queue and then traverses the queue.
  • Access the root node, the root node out of the queue, and the root node as the current element, respectively, the left node of the current element into the queue, the right node into the queue. (End of the first floor).
  • Record the number of elements in the current queue, take the left node of the previous step as the current element, access the value of the current element, the current element is dequeued (the number of elements is reduced by one), and the left node of the current element is queued and the right node is queued respectively.
  • Repeat until the number of recorded elements is 0, indicating the end of the layer.
  • This is repeated at each level until the entire queue is empty and the traversal is complete.

Convert to code as follows:

var levelOrder1 = function(root) {
    if (root == null) return []
    var arr = []
    arr.push(root) // The root node joins the queue
    var res = []

    while (arr.length) {
        var len = arr.length
        var floor = []// Store data for each layer
        while (len) {
            var temp = arr.shift()// The current element is out of the queue
            if(! temp)break
            // Each layer of data
            floor.push(temp.val)

            // The left node joins the queue
            if (temp.left) {
                arr.push(temp.left)
            }
            // The right node joins the queue
            if (temp.right) {
                arr.push(temp.right)
            }

            len--
        }
        // Store each layer of data
        res.push(floor)
    }

    return res
}
Copy the code

If we don’t use recursion, we can use the stack to get the result of traversal. The stack is a linear data structure, which follows the rule of “first in, last out”. In JavaScript, since there is no stack data structure, we can use the Array to simulate the traversal.

var stack = [] / / stack
stack.push(1)/ / 1 stack
stack.push(2)/ / into the stack 2
stack.push(3)/ / into the stack 3

// in this case, the stack elements are: [1,2,3]

stack.pop()/ / out 3 stack
stack.pop()/ / two stacks
Copy the code

Preorder traversal:

  • The root node pushes the stack, and the top element is retrieved accordingly.
  • Access the top element and exit the stack at the same time. The top element is the current element. The right node of the current element is pushed into the stack, and the left node of the current element is pushed into the stack.
  • Repeat until the entire stack is empty, and the traversal is complete.
var preorderTraversal = function(root) {
    var arr = []
    arr.push(root)
    var res = []
    while (arr.length) {
        var temp = arr.pop()
        if(! temp)break

        res.push(temp.val)

        if (temp.right) {
            arr.push(temp.right)
        }

        if (temp.left) {
            arr.push(temp.left)
        }
        
    }

    return res
};
Copy the code

In order traversal:

  • The loop pushes the root node and its left subtree onto the stack.
  • Until the left subtree is empty, access the top element of the stack, while the top element as the current element, and out of the stack.
  • Start to access the right subtree, loop out of the stack until the stack is empty, the traversal is finished.
var inorderTraversal = function(root) {
    var res = []
    var arr = []

    while(arr.length || root) {
        if (root) {
            arr.push(root)
            root = root.left
        } else {
            var temp = arr.pop()
            res.push(temp.val)
            root = temp.right
        }
    }

    return res
};
Copy the code

Post-order traversal:

This is the opposite of the idea of preorder traversal.

var postorderTraversal = function(root) {
    var arr = []
    arr.push(root)
    var res = []
    while(arr.length) {
        var temp = arr.pop()
        if(! temp)break
        res.unshift(temp.val)// Insert data from front to back
        if(temp.left) {// Push the left node first
            arr.push(temp.left)
        }
        if(temp.right) {
            arr.push(temp.right)
        }
    }

    return res
};
Copy the code

Complexity analysis:

  • Recursive implementation of binary tree traversal, each node only needs to traverse once, so the time complexity is O(n). We use recursion, and in the worst case the depth of the recursive call is O(n), so the space complexity is O(n).

  • The non-recursive implementation of binary tree traversal requires only one traversal per node, so the time complexity is O(n). While using the stack, the space complexity is the height of the binary tree, so the space complexity is O(n).

Binary tree traversal takes a basic binary tree operation, and mastering traversal skills is the basis for subsequent binary tree related operations.