Comprobar si un árbol binario es un árbol binario completo o no | Enfoque iterativo

Dado un árbol binario que contiene n Nodes. El problema es verificar si el árbol binario dado es un árbol binario completo o no. Un árbol binario completo se define como un árbol binario en el que todos los Nodes tienen cero o dos Nodes secundarios. Por el contrario, no hay ningún Node en un árbol binario completo, que tiene solo un Node hijo. 

Ejemplos: 

Input : 
           1
         /   \
        2     3
       / \  
      4   5
Output : Yes

Input :
           1
         /   \
        2     3
       /  
      4   
Output :No

Enfoque: En la publicación anterior se ha discutido una solución recursiva. En este post se ha seguido un enfoque iterativo. Realice un recorrido de orden de nivel iterativo del árbol utilizando la cola. Para cada Node encontrado, siga los pasos que se indican a continuación:

1. Si (Node->izquierda == NULL && Node->derecha == NULL), es un Node hoja. Deséchelo y comience a procesar el siguiente Node de la cola.
2. Si (Node->izquierda == NULL || Node->derecha == NULL), significa que solo está presente el hijo del Node . Devuelve false ya que el árbol binario no es un árbol binario completo.
3. De lo contrario, empuje los elementos secundarios izquierdo y derecho del Node a la cola.

Si todos los Nodes de la cola se procesan sin devolver falso, devuelve verdadero ya que el árbol binario es un árbol binario completo.

// C++ implementation to check whether a binary
// tree is a full binary tree or not
#include <bits/stdc++.h>
using namespace std;
 
// structure of a node of binary tree
struct Node {
    int data;
    Node *left, *right;
};
 
// function to get a new node
Node* getNode(int data)
{
    // allocate space
    Node* newNode = (Node*)malloc(sizeof(Node));
 
    // put in the data
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
// function to check whether a binary tree
// is a full binary tree or not
bool isFullBinaryTree(Node* root)
{
    // if tree is empty
    if (!root)
        return true;
 
    // queue used for level order traversal
    queue<Node*> q;
 
    // push 'root' to 'q'
    q.push(root);
 
    // traverse all the nodes of the binary tree
    // level by level until queue is empty
    while (!q.empty()) {
        // get the pointer to 'node' at front
        // of queue
        Node* node = q.front();
        q.pop();
 
        // if it is a leaf node then continue
        if (node->left == NULL && node->right == NULL)
            continue;
 
        // if either of the child is not null and the
        // other one is null, then binary tree is not
        // a full binary tee
        if (node->left == NULL || node->right == NULL)
            return false;
 
        // push left and right childs of 'node'
        // on to the queue 'q'
        q.push(node->left);
        q.push(node->right);
    }
 
    // binary tree is a full binary tee
    return true;
}
 
// Driver program to test above
int main()
{
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
 
    if (isFullBinaryTree(root))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation to check whether a binary
// tree is a full binary tree or not
import java.util.*;
class GfG {
 
// structure of a node of binary tree
static class Node {
    int data;
    Node left, right;
}
 
// function to get a new node
static Node getNode(int data)
{
    // allocate space
    Node newNode = new Node();
 
    // put in the data
    newNode.data = data;
    newNode.left = null;
    newNode.right = null;
    return newNode;
}
 
// function to check whether a binary tree
// is a full binary tree or not
static boolean isFullBinaryTree(Node root)
{
    // if tree is empty
    if (root == null)
        return true;
 
    // queue used for level order traversal
    Queue<Node> q = new LinkedList<Node> ();
 
    // push 'root' to 'q'
    q.add(root);
 
    // traverse all the nodes of the binary tree
    // level by level until queue is empty
    while (!q.isEmpty()) {
        // get the pointer to 'node' at front
        // of queue
        Node node = q.peek();
        q.remove();
 
        // if it is a leaf node then continue
        if (node.left == null && node.right == null)
            continue;
 
        // if either of the child is not null and the
        // other one is null, then binary tree is not
        // a full binary tee
        if (node.left == null || node.right == null)
            return false;
 
        // push left and right childs of 'node'
        // on to the queue 'q'
        q.add(node.left);
        q.add(node.right);
    }
 
    // binary tree is a full binary tee
    return true;
}
 
// Driver program to test above
public static void main(String[] args)
{
    Node root = getNode(1);
    root.left = getNode(2);
    root.right = getNode(3);
    root.left.left = getNode(4);
    root.left.right = getNode(5);
 
    if (isFullBinaryTree(root))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}

# Python3 program to find deepest
# left leaf Binary search Tree
 
# Helper function that allocates a 
# new node with the given data and
# None left and right pairs.                                    
class getNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# function to check whether a binary 
# tree is a full binary tree or not
def isFullBinaryTree( root) :
 
    # if tree is empty
    if (not root) :
        return True
 
    # queue used for level order
    # traversal
    q = []
 
    # append 'root' to 'q'
    q.append(root)
 
    # traverse all the nodes of the
    # binary tree level by level
    # until queue is empty
    while (not len(q)):
         
        # get the pointer to 'node'
        # at front of queue
        node = q[0]
        q.pop(0)
 
        # if it is a leaf node then continue
        if (node.left == None and
            node.right == None):
            continue
 
        # if either of the child is not None 
        # and the other one is None, then
        # binary tree is not a full binary tee
        if (node.left == None or
            node.right == None):
            return False
 
        # append left and right childs
        # of 'node' on to the queue 'q'
        q.append(node.left)
        q.append(node.right)
     
    # binary tree is a full binary tee
    return True
 
# Driver Code
if __name__ == '__main__':
    root = getNode(1)
    root.left = getNode(2)
    root.right = getNode(3)
    root.left.left = getNode(4)
    root.left.right = getNode(5)
 
    if (isFullBinaryTree(root)) :
        print("Yes" )
    else:
        print("No")
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# implementation to check whether a binary
// tree is a full binary tree or not
using System;
using System.Collections.Generic;
 
class GfG
{
 
// structure of a node of binary tree
public class Node
{
    public int data;
    public Node left, right;
}
 
// function to get a new node
static Node getNode(int data)
{
    // allocate space
    Node newNode = new Node();
 
    // put in the data
    newNode.data = data;
    newNode.left = null;
    newNode.right = null;
    return newNode;
}
 
// function to check whether a binary tree
// is a full binary tree or not
static bool isFullBinaryTree(Node root)
{
    // if tree is empty
    if (root == null)
        return true;
 
    // queue used for level order traversal
    Queue<Node> q = new Queue<Node> ();
 
    // push 'root' to 'q'
    q.Enqueue(root);
 
    // traverse all the nodes of the binary tree
    // level by level until queue is empty
    while (q.Count!=0) {
        // get the pointer to 'node' at front
        // of queue
        Node node = q.Peek();
        q.Dequeue();
 
        // if it is a leaf node then continue
        if (node.left == null && node.right == null)
            continue;
 
        // if either of the child is not null and the
        // other one is null, then binary tree is not
        // a full binary tee
        if (node.left == null || node.right == null)
            return false;
 
        // push left and right childs of 'node'
        // on to the queue 'q'
        q.Enqueue(node.left);
        q.Enqueue(node.right);
    }
 
    // binary tree is a full binary tee
    return true;
}
 
// Driver code
public static void Main(String[] args)
{
    Node root = getNode(1);
    root.left = getNode(2);
    root.right = getNode(3);
    root.left.left = getNode(4);
    root.left.right = getNode(5);
 
    if (isFullBinaryTree(root))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
 
// This code has been contributed by 29AjayKumar

<script>
 
    // JavaScript implementation to check whether a binary
    // tree is a full binary tree or not
     
    // A Binary Tree Node
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
 
    // function to get a new node
    function getNode(data)
    {
        // allocate space
        let newNode = new Node(data);
        return newNode;
    }
 
    // function to check whether a binary tree
    // is a full binary tree or not
    function isFullBinaryTree(root)
    {
        // if tree is empty
        if (root == null)
            return true;
 
        // queue used for level order traversal
        let q = [];
 
        // push 'root' to 'q'
        q.push(root);
 
        // traverse all the nodes of the binary tree
        // level by level until queue is empty
        while (q.length > 0) {
            // get the pointer to 'node' at front
            // of queue
            let node = q[0];
            q.shift();
 
            // if it is a leaf node then continue
            if (node.left == null && node.right == null)
                continue;
 
            // if either of the child is not null and the
            // other one is null, then binary tree is not
            // a full binary tee
            if (node.left == null || node.right == null)
                return false;
 
            // push left and right childs of 'node'
            // on to the queue 'q'
            q.push(node.left);
            q.push(node.right);
        }
 
        // binary tree is a full binary tee
        return true;
    }
     
    let root = getNode(1);
    root.left = getNode(2);
    root.right = getNode(3);
    root.left.left = getNode(4);
    root.left.right = getNode(5);
   
    if (isFullBinaryTree(root))
        document.write("Yes");
    else
        document.write("No");
   
</script>

Yes

Complejidad temporal: O(n). 
Espacio auxiliar: O(max), donde max es el número máximo de Nodes en un nivel particular.