FAQs on Properties of Binary Tree
Q: What is a Binary Tree?
A: A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child.
Q: What are the main properties of a Binary Tree?
A:
- Each node has at most two children.
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary tree.
Q: What are the types of Binary Trees?
A:
- Full Binary Tree: A binary tree in which every node other than the leaves has two children.
- Complete Binary Tree: A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
- Perfect Binary Tree: A binary tree in which all internal nodes have two children and all leaf nodes are at the same level.
- Balanced Binary Tree: A binary tree in which the depth of the left and right subtrees of any node differ by at most one.
- Degenerate (or pathological) Tree: A tree where each parent node has only one associated child node.
Q: How to implement a Binary Tree in code?
A: Here is the code.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# Example Usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
Q: How to traverse a Binary Tree?
A:
- Inorder Traversal: Traverse left subtree, visit root, traverse right subtree.
- Preorder Traversal: Visit root, traverse left subtree, traverse right subtree.
- Postorder Traversal: Traverse left subtree, traverse right subtree, visit root.
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
# Example Usage
inorder_traversal(root)
Q: How to check if a Binary Tree is balanced?
A: Here is the code.
def is_balanced(root):
if root is None:
return True
left_height = height(root.left)
right_height = height(root.right)
return abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right)
Q: How to find the height of a Binary Tree?
A: Here is the code.
def height(root):
if root is None:
return 0
else:
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1
Q: How to check if a Binary Tree is symmetric?
A: Here is the code.
def is_symmetric(root):
def is_mirror(left, right):
if left is None and right is None:
return True
if left is None or right is None:
return False
return (left.val == right.val) and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
if root is None:
return True
return is_mirror(root.left, root.right)
Important Interview Questions and Answers on Properties of Binary Tree
Q: What is a binary tree?
A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child.
Q: What is the height of a binary tree?
The height of a binary tree is the maximum number of edges in any path from the root node to a leaf node.
Q: What is the depth of a node in a binary tree?
The depth of a node in a binary tree is the number of edges from the root to that node.
Q: What is a complete binary tree?
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Q: What is a full binary tree?
A full binary tree is a binary tree in which every node other than the leaves has two children.
Q: What is a perfect binary tree?
A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
Q: What is a balanced binary tree?
A balanced binary tree is a binary tree in which the height of the left and right subtrees of any node differ by no more than one.
Q: How do you find the height of a binary tree recursively?
Here's an example code in Python:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def height(root):
if root is None:
return -1
left_height = height(root.left)
right_height = height(root.right)
return 1 + max(left_height, right_height)
# Example usage:
# Constructing a binary tree
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print("Height of the binary tree:", height(root)) # Output: 2
Q: How do you check if a binary tree is balanced?
Here's an example code in Python:
def is_balanced(root):
return check_height(root) != -1
def check_height(root):
if root is None:
return 0
left_height = check_height(root.left)
if left_height == -1:
return -1
right_height = check_height(root.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return 1 + max(left_height, right_height)
# Example usage:
# Constructing a binary tree
# 1
# / \
# 2 3
# / \ / \
# 4 5 6 7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print("Is the binary tree balanced?", is_balanced(root)) # Output: True
