I’ve interviewed with a number of companies and they all ask questions about binary trees, such as these:

  1. How many ways can a binary tree traverse
  2. How do you traverse a binary tree without recursion
  3. How can we tell if a binary tree is a symmetric binary tree
  4. Flip the left and right nodes of the binary tree
  5. Implement a function to receive any binary tree, find the sum of all the binary tree root to leaf path of the number

The front end often test algorithm is binary tree and sort, these seem to many companies will have one or two such topics, you can focus on these knowledge points before the interview, this article mainly explains binary tree.

Basic knowledge of

Before we can understand binary trees we need to know what a binary tree is and what a binary tree is made of.

A binary tree has no more than two nodes per node. The topmost node of a tree is called the root node. If more than one node is connected below it, the node is called the parent node and the nodes below it are called the children nodes. A node can have zero or more children nodes

The following code creates a binary tree.

function Node(value, left, right) {
  this.value = value;
  this.left = left;
  this.right = right;
}

function BST() {
  this.root = null;
  this.insert = insert;
}

function insert(value) {
  let node = new Node(value, null.null)
  if (this.root == null) {
    / / the root node
    this.root = node;
  } else {
    / / child nodes
    let current = this.root;
    let parent;
    while (true) {
      parent = current;
      if (value < current.value) {
        current = current.left;
        if (current == null) {
          parent.left = node;
          break; }}else {
        current = current.right;
        if(current == null) {
          parent.right = node;
          break;
        }
      }
    }
  }
}

let tree = new BST()

tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
console.log(tree.root)
Copy the code

Insert method is to enter and exit a node into the binary tree, we need to judge the position of the node, compare the size of the left and right nodes respectively, and then selectively input into it.

Practical subject

There are 5 interview questions at the beginning of the article.

Q: What are the traversal methods of binary trees?

Answer: There are three traversal methods, middle order, first order, after order. Middle order traversal Accesses all nodes in the binary tree in ascending order based on their key values. Sequential traversal first accesses the root node and then the left and right subtrees in the same manner. A back-order traversal visits the leaf node first, from the left to the right subtree, and then to the root node.

The following is the path diagram for mid-order traversal, 10->22->30->56->77->81->92 (according to the ascending access rule)

// middle order traversal
function inOrder(node) {
  let result = []
  if(! (node ==null)) {
    inOrder(node.left)
    result.push(node.value)
    inOrder(node.right)
  }
  return result
}
let tree = new BST()
tree.insert(56)
tree.insert(22)
tree.insert(81)
tree.insert(10)
tree.insert(30)
tree.insert(77)
tree.insert(92)
inOrder(tree.root)
Copy the code

The following is the path diagram of sequential traversal, 50->10->5->15->70->60->80 (according to the first root node and then child node)

// order traversal first
function preOrder(node) {
  let result = []
  if(! (node ==null)) {
    result.push(node.value)
    preOrder(node.left)
    preOrder(node.right)
  }
  return result
}
let tree = new BST()
tree.insert(50)
tree.insert(10)
tree.insert(70)
tree.insert(5)
tree.insert(15)
tree.insert(60)
tree.insert(80)
preOrder(tree.root)
Copy the code

The following figure is the path diagram of sequential traversal, 3->22->16->37->99->45->23 (according to the first child node and then the root node)

// after the sequence traversal
function postOrder(node) {
  let result = []
  if(! (node ==null)) {
    postOrder(node.left)
    postOrder(node.right)
    result.push(node.value)
  }
  return result
}
let tree = new BST()
tree.insert(23)
tree.insert(16)
tree.insert(45)
tree.insert(3)
tree.insert(22)
tree.insert(37)
tree.insert(99)
postOrder(tree.root)
Copy the code

Q: How do I traverse a binary tree without recursion?

The insert method in the code does not make recursion but uses a while loop, if you have noticed. Now I’m going to iterate again by using while.

To loop through a binary tree you must also use a stack for backtracking algorithms.

// middle order traversal
function inOrder(node) {
  let stack = []
  let result = []
  let parent = node;
  while(parent ! = =null || stack.length) {
    if(parent ! = =null) {
      stack.push(parent)
      parent = parent.left
    } else {
      parent = stack.pop()
      result.push(parent.value)
      parent = parent.right
    }
  }
  console.log(result)
}
Copy the code
// order traversal first
function preOrder(node) {
  let stack = []
  stack.push(node)
  let result = []
  while(stack.length ! = =0) {
    let parent = stack.pop()
    if(parent.right ! = =null) {
      stack.push(parent.right)
    }
    if(parent.left ! = =null) {
      stack.push(parent.left)
    }
    result.push(parent.value)
  }
  console.log(result)
}
Copy the code
// after the sequence traversal
function postOrder(node) {
  let stack = []
  stack.push(node)
  let result = []
  let parent = node
  while(stack.length ! = =0) {
    parent = stack.pop()
    if(parent.left ! = =null) {
      stack.push(parent.left)
    }
    if(parent.right ! = =null) {
      stack.push(parent.right)
    }
    result.unshift(parent.value)
  }
  console.log(result)
}
Copy the code

Here is an article called “Non-recursive Binary tree Pre-order, middle order, and post-order Traversal” that explains the idea of code implementation. But it’s written in Java code, haha!

If you are not familiar with stack data structures, you can read my previous article “Interview questions on JS parenthesis Matching”.

conclusion

First order: root left and right, middle order: left root right, subsequent: left and right root.

Here is a sentence, depth first and breadth first sentiment, “depth first search is the order traversal of the tree”, “breadth first search is the tree by layer traversal”.

Depth-first, sequential traversal ABEFGCD

Breadth-first, traversing ABCDEFG layer by layer

Q: How can we tell if a binary tree is a symmetric one

A tree is symmetric if its left subtree mirrors its right subtree.

Given a binary tree, check whether it is mirror – symmetric.

var node1 = {
  value: 1.left: {
    value: 2.left: {
      value: 3
    },
    right: {
      value: 4}},right: {
    value: 2.left: {
      value: 4
    },
    right: {
      value: 3}}}Copy the code

recursive

function isSymmetric (root) {
  return isMirror(root, root)
}

function isMirror (t1, t2) {
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  return (t1.value === t2.value) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right)
}

console.log(isSymmetric(node1))
Copy the code

Q: Flip the left and right nodes of the binary tree

Original problem: The data structure of a binary tree is as follows. You need to flip each node of the binary tree left and right

var node1 = {
  value: 1.left: {
    value: 2.left: {
      value: 4
    },
    right: {
      value: 5}},right: {
    value: 3.left: {
      value: 6
    },
    right: {
      value: 7}}}Copy the code

Ideas:

  1. Switch the left and right nodes first
  2. Recurse to the child nodes
function reverse(node) {
  if(node ! =null) {
    lettemp = node.left; node.left = node.right; node.right = temp; reverse(node.left); reverse(node.right); }}Copy the code

Secretly tell you, this topic is a didi interview question, feel very difficult! Ha ha.

5. Implement a function to receive any binary tree and find the sum of the numbers from the root node to the leaf path of the binary tree

function getPathSum(root) {
  let total = 0
  function next(node) {
    if(node ! =undefined) {
      total += node.value
      next(node.left)
      next(node.right)
    }
  }
  next(root)
  return total
}
Copy the code

It’s done using a sequential traversal

GetPathSum (node) returns 7=(1+2)+(1+3)

var node = {
  value: 1.left: {
    value: 2.left: null.right: null
  },
  right: {
    value: 3.left: null.right: null}}Copy the code

Traverse in order of precedence

function getPathSum(root) {
  let total = 0
  let left = []
  let right = []
  function next(node, flag) {
    if(node ! =undefined) {
      if (flag === 0) {
        left.push(node.value)
        right.push(node.value)
        total = node.value + node.value
      }
      if (flag === 1) {
        left.push(node.value)
        total += node.value
      }
      if (flag === 2) {
        total += node.value
        right.push(node.value)
      }
      next(node.left, 1)
      next(node.right, 2)
    }
  }
  next(root, 0)
  return `${total}= (${left.join('+')}) + (${right.join('+')}) `
}
Copy the code

These are some of the topics I interviewed recently. How do you feel about them?

If you have any questions, please comment.