Hello:

Today, I meet my friends again. Recently, I have been doing a topic related to binary trees. Today, I will share with you a topic related to “Judging whether it is a complete binary tree”.

Determine whether it is a complete binary tree

View all source code: click to view all source code

Intro – What is a complete binary tree?

Take a look at this picture:

This is a binary tree, how do you tell if it’s a complete binary tree?

  • When a node has right children but no left children, the tree is considered incomplete
  • A node is considered a complete binary tree when its left child exists but its right child does not
  • If there are no children, the tree is considered complete only if there are no children from left to right, as in Figure 2

And the first picture above this binary tree is clearly an incomplete binary tree, because at the third level it has no right child nodes at node 2. One node is separated between nodes 6 and 4 (node 2 has no right child node), so it is not a complete binary tree

Look at the picture again, the tree is a complete binary tree, while the single node 3 no right child nodes, but there is no gap between the 6, 4, 5 nodes of child nodes, it explains the article 3 of the above said (how no child node, it is on the left to the right, in turn, there is no child node just as a complete binary tree)

process

This problem can be solved by using the layer-traversal method:

  • Prepare a queue first, and using the queue through layers is the best solution
  • We first add the head node to the queue (if the head node is empty, you can either think of it as an incomplete binary tree or a complete binary tree)
  • Traversal of the queue breaks out traversal conditions until the queue is empty
  • In this case, we need to prepare a Bool variable and set it to true if the left or right child of a node does not exist
  • The tree is an incomplete binary tree when the Bool variable is true and the left or right child of the remaining node is not empty
  • When the left child node of a tree does not exist and the right child node does exist, the tree is also an incomplete binary tree

code

Tree node

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}
Copy the code

The test code

func main(a) {
	root := &TreeNode{val: "1"}
	root.left = &TreeNode{val: "2"}
	root.left.left = &TreeNode{val: "4"}
	root.left.right = &TreeNode{val: "10"}
	root.left.left.left = &TreeNode{val: "Seven"}
	root.right = &TreeNode{val: "3"}
	root.right.left = &TreeNode{val: "5"}
	root.right.right = &TreeNode{val: "6"}
	if IsCompleteBt(root) {
		fmt.Println("Is a perfect binary tree.")}else {
		fmt.Println("Not a perfect binary tree.")}}Copy the code

Determine whether the tree is a complete binary tree code

// IsCompleteBt where the default root node is null and belongs to a complete binary tree. This can be defined by itself as a complete binary tree or not
func IsCompleteBt(root *TreeNode) bool {
	if root == nil {
		return true
	}

	/** * condition: * 1. If a node has a right child but no left child, the tree is considered incomplete. * 2. A node is considered a complete binary tree */ when its left child exists but its right child does not
	var tempNodeQueue []*TreeNode

	tempNodeQueue = append(tempNodeQueue, root)

	var tempNode *TreeNode
	isSingleNode := false
	for len(tempNodeQueue) ! =0 {
		tempNode = tempNodeQueue[0]
		tempNodeQueue = tempNodeQueue[1:]

		if(isSingleNode && (tempNode.left ! =nil|| tempNode.right ! =nil)) || (tempNode.left == nil&& tempNode.right ! =nil) {return false
		}

		iftempNode.left ! =nil{
			tempNodeQueue = append(tempNodeQueue,tempNode.left)
		}else{
			isSingleNode = true
		}

		iftempNode.right ! =nil {
			tempNodeQueue = append(tempNodeQueue, tempNode.right)
		}else{
			isSingleNode = true}}return true
}
Copy the code

Code reading

There’s not much to say in this code, just say the first if in for

Let’s look at the last two conditions in the process above, and only when the last two conditions are met can we determine whether the tree is a complete binary tree.

Also because the implementation of determining whether a full binary tree is a full binary tree is handled by traversing the tree, because traversing the tree by layer can be implemented singly through the queue. That’s why we’re using queues

Here’s why we want to create a separate isSingleNode variable:

  • Because if you have a node on the left or a node on the right, if you have a non-empty node behind the same layer, then the tree is not a full binary tree. Look at the figure below

At the end of the tree layer of green paint duck is less of a node, so I use a variable I identify the current node (2) in the above said node child nodes is a less, less if the current node (2) in the above said node of the next node (3) in the above said node child nodes (4 and 5) in the above said if there is not fully binary tree, So that’s what creating an isSingleNode variable does

The results