Binary Tree Data Structure Questions

4 5 2 3 1

1 2 4 5 3

1 3 2 4 5

4 2 5 1 3

2^(h+1) - 1

h^2

2h

2^h - 1

k + 1

k

2k

2k + 1

It is not possible to identify leaf nodes during preorder traversal.

A node is a leaf if it is visited before its children.

A node is a leaf if both its left and right child pointers are NULL.

A node is a leaf if its value is less than its parent's value.

O(n log n)

O(1)

O(n)

O(log n)

Depth = Index / 2

Depth = log2(Index + 1)

Depth = Index

Depth = 2 * Index

There is no significant difference; both traversals produce the same output.

Postorder is used for deleting nodes in a Binary Tree, while Inorder is used for printing the nodes in sorted order.

Postorder visits the root node before its children, while Inorder visits the root between its left and right children.

Postorder visits the left subtree, then the right subtree, and finally the root, while Inorder visits the left subtree, the root, and then the right subtree.

Height and depth are the same thing.

Height is the number of edges from the node to the deepest leaf, while depth is the number of edges from the root to the node.

Height is the number of edges from the root to the node, while depth is the number of nodes from the root to the node.

Height is always one more than the depth of a node.

Perfect Binary Tree

Full Binary Tree

Skewed Binary Tree

Complete Binary Tree

O(n log n)

O(n)

O(log n)

O(n^2)