Problem

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-nary tree structure.

For example, you may encode the following 3-ary tree to a binary tree in this way:

graph LR
	subgraph Original[" "]
	    A(1)
	    A --- B(3)
	    A --- C(2)
	    A --- D(4)
	    B --- E(5)
	    B --- F(6)
	end

	subgraph Encoded[" "]
	    A2(1)
	    A2 --- B2(3)
	    A2 --- C2(2)
	    B2 --- E2(5)
	    B2 ~~~ N2:::hidden
	    C2 ~~~ N1:::hidden
	    C2 --- D2(4)
	    E2 ~~~ N3:::hidden
	    E2 --- F2(6)
	end

Original --> Encoded

classDef hidden display:none

Note that the above is just an example which might or might not work. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note:

  1. N is in the range of [1, 1000]
  2. Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

Examples

Example 1

1
2

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]

Example 2

1
2

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

Solution

Method 1 - DFS

Encoding an N-ary tree into a binary tree involves transforming the structure of the tree while preserving the connectivity. The approach can involve two main transformations:

  1. Left-child/right-sibling representation:
    • The first child of a node becomes the left child in the binary tree.
    • Subsequent children become the right child of the previous child, forming a sibling chain.
  2. Decoding:
    • Reverse the transformation by reconstructing the N-ary tree from the binary tree.

This encoding effectively maintains the N-ary relationships while conforming to the binary tree structure.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Codec {
    // Method to encode N-ary tree (Node) to Binary tree (TreeNode)
    public TreeNode encode(Node root) {
        if (root == null) return null;
        TreeNode ans = new TreeNode(root.val);
        if (root.children == null || root.children.isEmpty()) return ans;

        // First child becomes the left child
        ans.left = encode(root.children.get(0));
        TreeNode curr = ans.left;

        // Subsequent children are linked as right siblings
        for (int i = 1; i < root.children.size(); i++) {
            curr.right = encode(root.children.get(i));
            curr = curr.right;
        }
        return ans;
    }

    // Method to decode Binary tree (TreeNode) back to N-ary tree (Node)
    public Node decode(TreeNode root) {
        if (root == null) return null;
        Node ans = new Node(root.val, new ArrayList<>());
        TreeNode curr = root.left;

        // Expand the left child chain into the children list
        while (curr != null) {
            ans.children.add(decode(curr));
            curr = curr.right;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Node:
    def __init__(self, val: int, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children if children is not None else []

class TreeNode:
    def __init__(self, val: int, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    # Method to encode N-ary tree (Node) to Binary tree (TreeNode)
    def encode(self, root: Optional[Node]) -> Optional[TreeNode]:
        if not root:
            return None
        ans = TreeNode(root.val)
        if not root.children:
            return ans
        
        # First child becomes the left child
        ans.left = self.encode(root.children[0])
        curr = ans.left
        
        # Subsequent children are linked as right siblings
        for i in range(1, len(root.children)):
            curr.right = self.encode(root.children[i])
            curr = curr.right
        return ans

    # Method to decode Binary tree (TreeNode) back to N-ary tree (Node)
    def decode(self, root: Optional[TreeNode]) -> Optional[Node]:
        if not root:
            return None
        ans = Node(root.val, [])
        curr = root.left
        
        # Expand the left child chain into the children list
        while curr:
            ans.children.append(self.decode(curr))
            curr = curr.right
        return ans

Complexity

  • ⏰ Time complexity: O(n). We traverse all nodes once in a DFS manner. Thus, both processes have O(n) complexity, where n is the total number of nodes.
  • 🧺 Space complexity: O(h). The space used for recursion (call stack) in DFS traversal is proportional to the height of the tree. Hence, it is O(h) where h is the height of the tree.