Binary Tree Data Structure Questions

What is the output of this Python code that performs a Level Order Traversal (BFS) on a Binary Tree?

from collections import deque

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def level_order(root):
    if root is None:
        return
    nodes = deque([root])
    while(len(nodes) > 0):
        curr = nodes.popleft()
        print(curr.data, end=' ')
        if curr.left:
            nodes.append(curr.left)
        if curr.right:
            nodes.append(curr.right)

# Binary Tree Construction
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

level_order(root)

What is the key difference between single threading and double threading in a Threaded Binary Tree?

When constructing a Segment Tree for a given array, what information is typically stored in each node of the Segment Tree?

You are given a binary tree where nodes have an additional pointer 'next'. This 'next' pointer is initially null. Design an algorithm to populate each next pointer to point to its right sibling. If there is no right sibling, the next pointer should remain null. Can this be done efficiently without using recursion?

You want to print the nodes of a binary tree in a way that nodes at the same level are printed together, from left to right. Which traversal method achieves this?

What is the primary advantage of using a Complete Binary Tree for implementing a Heap data structure?

Consider this Python code aiming to check if a Binary Tree is a Binary Search Tree (BST). Does it function correctly?

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def is_bst(root):
    if root is None:
        return True
    if root.left and root.left.data > root.data:
        return False
    if root.right and root.right.data < root.data:
        return False
    return is_bst(root.left) and is_bst(root.right)

You need to transmit a large file containing English text. Using a Huffman tree, which of these characters is likely to have the shortest codeword?

Given this C++ code snippet for a Binary Search Tree (BST), what will the tree look like after the following insertions: 5, 3, 8, 1, 4, 7, 9?

struct Node {
    int data;
    Node *left, *right;
};

Node* insert(Node* node, int data) {
    if (node == NULL) {
        return new Node(data);
    }
    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    }
    return node;
}

Examine this Python code attempting to find the diameter of a Binary Tree. Is it implemented correctly?

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def diameter(root):
    if root is None:
        return 0
    lheight = height(root.left)
    rheight = height(root.right)
    return max(lheight + rheight + 1, max(diameter(root.left), diameter(root.right)))

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))