Skip to content

431. Encode N-ary Tree to Binary Tree 👍

Approach 1: BFS

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Codec {
 public:
  // Encodes an n-ary tree to a binary tree.
  TreeNode* encode(Node* root) {
    if (root == nullptr)
      return nullptr;

    TreeNode* rootTreeNode = new TreeNode(root->val);
    queue<pair<Node*, TreeNode*>> q{{{root, rootTreeNode}}};

    while (!q.empty()) {
      const auto [parentNode, parentTreeNode] = q.front();
      q.pop();
      TreeNode* prevTreeNode = nullptr;
      TreeNode* headTreeNode = nullptr;
      for (Node* child : parentNode->children) {
        TreeNode* currTreeNode = new TreeNode(child->val);
        if (prevTreeNode != nullptr)
          prevTreeNode->right = currTreeNode;
        else
          headTreeNode = currTreeNode;
        prevTreeNode = currTreeNode;
        q.emplace(child, currTreeNode);
      }
      parentTreeNode->left = headTreeNode;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  Node* decode(TreeNode* root) {
    if (root == nullptr)
      return nullptr;

    Node* rootNode = new Node(root->val);
    queue<pair<Node*, TreeNode*>> q{{{rootNode, root}}};

    while (!q.empty()) {
      const auto [parentNode, parentTreeNode] = q.front();
      q.pop();
      TreeNode* sibling = parentTreeNode->left;
      while (sibling) {
        Node* currNode = new Node(sibling->val);
        parentNode->children.push_back(currNode);
        q.emplace(currNode, sibling);
        sibling = sibling->right;
      }
    }

    return rootNode;
  }
};

 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
class Codec {
  // Encodes an n-ary tree to a binary tree.
  public TreeNode encode(Node root) {
    if (root == null)
      return null;

    TreeNode rootTreeNode = new TreeNode(root.val);
    Queue<Pair<Node, TreeNode>> q = new ArrayDeque<>(Arrays.asList(new Pair<>(root, rootTreeNode)));

    while (!q.isEmpty()) {
      Node parentNode = q.peek().getKey();
      TreeNode parentTreeNode = q.poll().getValue();
      TreeNode prevTreeNode = null;
      TreeNode headTreeNode = null;
      for (Node child : parentNode.children) {
        TreeNode currTreeNode = new TreeNode(child.val);
        if (prevTreeNode == null)
          headTreeNode = currTreeNode;
        else
          prevTreeNode.right = currTreeNode;
        prevTreeNode = currTreeNode;
        q.offer(new Pair<>(child, currTreeNode));
      }
      parentTreeNode.left = headTreeNode;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  public Node decode(TreeNode root) {
    if (root == null)
      return null;

    Node rootNode = new Node(root.val, new ArrayList<>());
    Queue<Pair<Node, TreeNode>> q = new ArrayDeque<>(Arrays.asList(new Pair<>(rootNode, root)));

    while (!q.isEmpty()) {
      Node parentNode = q.peek().getKey();
      TreeNode parentTreeNode = q.poll().getValue();
      TreeNode sibling = parentTreeNode.left;
      while (sibling != null) {
        Node currNode = new Node(sibling.val, new ArrayList<>());
        parentNode.children.add(currNode);
        q.offer(new Pair<>(currNode, sibling));
        sibling = sibling.right;
      }
    }

    return rootNode;
  }
}

 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
class Codec:
  # Encodes an n-ary tree to a binary tree.
  def encode(self, root: 'Node') -> Optional[TreeNode]:
    if not root:
      return None

    rootTreeNode = TreeNode(root.val)
    q = collections.deque([(root, rootTreeNode)])

    while q:
      parentNode, parentTreeNode = q.popleft()
      prevTreeNode = None
      headTreeNode = None
      for child in parentNode.children:
        currTreeNode = TreeNode(child.val)
        if prevTreeNode:
          prevTreeNode.right = currTreeNode
        else:
          headTreeNode = currTreeNode
        prevTreeNode = currTreeNode
        q.append((child, currTreeNode))
      parentTreeNode.left = headTreeNode

    return rootTreeNode

  # Decodes your binary tree to an n-ary tree.
  def decode(self, root: Optional[TreeNode]) -> 'Node':
    if not root:
      return None

    rootNode = Node(root.val, [])
    q = collections.deque([(rootNode, root)])

    while q:
      parentNode, parentTreeNode = q.popleft()
      sibling = parentTreeNode.left
      while sibling:
        currNode = Node(sibling.val, [])
        parentNode.children.append(currNode)
        q.append((currNode, sibling))
        sibling = sibling.right

    return rootNode

Approach 2: DFS

  • Time: $O(n)$
  • Space: $O(h)$
 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
class Codec {
 public:
  // Encodes an n-ary tree to a binary tree.
  TreeNode* encode(Node* root) {
    if (root == nullptr)
      return nullptr;

    TreeNode* rootTreeNode = new TreeNode(root->val);
    if (!root->children.empty())
      rootTreeNode->left = encode(root->children[0]);

    // The parent for the rest of the children
    TreeNode* currTreeNode = rootTreeNode->left;

    // Encode the rest of the children
    for (int i = 1; i < root->children.size(); ++i) {
      currTreeNode->right = encode(root->children[i]);
      currTreeNode = currTreeNode->right;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  Node* decode(TreeNode* root) {
    if (root == nullptr)
      return nullptr;

    Node* rootNode = new Node(root->val);
    TreeNode* currTreeNode = root->left;

    while (currTreeNode != nullptr) {
      rootNode->children.push_back(decode(currTreeNode));
      currTreeNode = currTreeNode->right;
    }

    return rootNode;
  }
};

 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
class Codec {
  // Encodes an n-ary tree to a binary tree.
  public TreeNode encode(Node root) {
    if (root == null)
      return null;

    TreeNode rootTreeNode = new TreeNode(root.val);
    if (!root.children.isEmpty())
      rootTreeNode.left = encode(root.children.get(0));

    // The parent for the rest of the children
    TreeNode currTreeNode = rootTreeNode.left;

    // Encode the rest of the children
    for (int i = 1; i < root.children.size(); ++i) {
      currTreeNode.right = encode(root.children.get(i));
      currTreeNode = currTreeNode.right;
    }

    return rootTreeNode;
  }

  // Decodes your binary tree to an n-ary tree.
  public Node decode(TreeNode root) {
    if (root == null)
      return null;

    Node rootNode = new Node(root.val, new ArrayList<>());
    TreeNode currTreeNode = root.left;

    while (currTreeNode != null) {
      rootNode.children.add(decode(currTreeNode));
      currTreeNode = currTreeNode.right;
    }

    return rootNode;
  }
}

 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
class Codec:
  # Encodes an n-ary tree to a binary tree.
  def encode(self, root: 'Node') -> Optional[TreeNode]:
    if not root:
      return None

    rootTreeNode = TreeNode(root.val)
    if root.children:
      rootTreeNode.left = self.encode(root.children[0])

    # The parent for the rest of the children
    currTreeNode = rootTreeNode.left

    # Encode the rest of the children
    for i in range(1, len(root.children)):
      currTreeNode.right = self.encode(root.children[i])
      currTreeNode = currTreeNode.right

    return rootTreeNode

  # Decodes your binary tree to an n-ary tree.
  def decode(self, root: Optional[TreeNode]) -> 'Node':
    if not root:
      return None

    rootNode = Node(root.val, [])
    currTreeNode = root.left

    while currTreeNode:
      rootNode.children.append(self.decode(currTreeNode))
      currTreeNode = currTreeNode.right

    return rootNode