We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Trees
  4. Swap Nodes [Algo]
  5. Discussions

Swap Nodes [Algo]

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

    You are viewing a single comment's thread. Return to all comments →

  • realq86 4 years ago+ 2 comments

    Solved the problem but had to. 1. Create node object. 2. Create a breathFirst to read input. 3. Create a depthFirst to change height. 4. Create a Inorder to print.

    Took 3 hours total. Is is listed as "Easy?" Is there an easier way than the apporche I did?

    39|
    Permalink
    • ludopulles 4 years ago+ 4 comments

      I'm not sure about your breadth-first approach to read input. You should just initialize your array of length n with left and right child.

      About the time, if you practice more, you will see that you can solve problems faster and faster! This one took me 10 minutes :).

      0|
      ParentPermalink
      • realq86 4 years ago+ 3 comments

        Hi, Thanks for the tip. So you mean you just used an array and didn't create a binary tree data structure?

        I actually created a tree, loaded it with data swap the subtree, and traverse the tree to print the output.

        Sounds like I over engineered! Would you like to exchange solutions?

        4|
        ParentPermalink
        • ludopulles 4 years ago+ 15 comments

          Hmm, well, I used an array but it represents a binary tree, so I would call it a binary tree data structure :P. Here is my solution: http://ideone.com/Fml7Sm You can see, I didn't use a BFS but I iterated over the array. This is possible because a swap won't change the depth of a node, so the order in which you swap nodes doesn't matter.

          51|
          ParentPermalink
          • realq86 4 years ago+ 0 comments

            You serialized the tree! In this case a good call, since the input is serialized to begin with.

            0|
            ParentPermalink
          • HarryCho 4 years ago+ 0 comments

            great answer!

            0|
            ParentPermalink
          • keyul 3 years ago+ 0 comments

            Thanks for idea of Two different arrays to store left and right node.

            0|
            ParentPermalink
          • raina_venki 3 years ago+ 1 comment

            Hi, your code is not giving any output for this following input...

            5

            2 2

            3 -1

            -1 3

            -1 -1

            -1 -1

            2

            1

            1

            0|
            ParentPermalink
            • ludopulles 3 years ago+ 3 comments

              The tree you give, is not a tree:

              1. the right child of node 3 is itself
              2. both the left and right child of node 1 are 2.

              So we can assume that this input won't appear as one of the test cases.

              1|
              ParentPermalink
              • raina_venki 3 years ago+ 0 comments

                sorry i didn't get you.... 1 is the root, 1st 2 is left child of 1 and 2nd 2 is the right child of 1,

                1st 3 is the left child of 1st 2 and right child of 1st 2 is null,

                2nd 3 is the right child of 2nd 2 and left child of 2nd 2 is null,

                both children of both 3 will be null.... this is the tree right.......

                0|
                ParentPermalink
              • raina_venki 3 years ago+ 1 comment

                and i don't understand why you mentioned that both left and right child of node 1 are 2.....yeah...i can be right....since it is a binary tree not a binary search tree....and there no such rule that there shouldn't be duplicate nodes....and both the children are greater than their parent....

                -1|
                ParentPermalink
                • ludopulles 3 years ago+ 1 comment

                  The 4th line of input is -1 3, which shows the left and right child of node 3. Nodes start from 1. So there is a cycle 3 -> 3. Therefore it is not a tree.

                  1|
                  ParentPermalink
                  • raina_venki 3 years ago+ 1 comment

                    that fourth line of input are children of the right child of root node right....not the children of 3....

                    0|
                    ParentPermalink
                    • ludopulles 3 years ago+ 1 comment

                      Uhm, no... Check the input format. It explains it quite well.

                      0|
                      ParentPermalink
                      • aayush_break 3 years ago+ 0 comments
                        [deleted]
                        0|
                        ParentPermalink
              • gschoen 3 years ago+ 2 comments

                It's a tree but with nodes that have duplicate data.

                     1
                    / \
                   2   2
                  /     \
                 3       3
                

                In this case, swapNodes won't change the nature of the tree.

                1|
                ParentPermalink
                • raina_venki 3 years ago+ 0 comments

                  it is not mentioned in the problem.....or in the input conditions........

                  0|
                  ParentPermalink
                • tvichvy 5 months ago+ 0 comments

                  There is no data (well, you could say node's own index is its payload). It's just a bunch of indexes. So the root has node number 2 as a left child and also a right child. And node number three has itself as a right child.

                  Not a tree. Somebody just doesn't understand the format. Which really isn't surprising given the poor description.

                  But if anyone wants it blow by blow:

                  • 5 // there are five nodes
                  • 2 2 // root (node 1) has node 2 as left child and node 2 as right child
                  • 3 -1 // node 2 has node 3 as left child
                  • -1 3 // node 3 has node 3 as right child
                  • -1 -1 // node 4 has no children
                  • -1 -1 // node 5 is the same
                  0|
                  ParentPermalink
          • aj510 3 years ago+ 0 comments

            Wow, very nice! I did the same as realq86 (created tree data struct and methods). Thank you for sharing your code! Clever :D

            -1|
            ParentPermalink
          • Zen_Programmer 3 years ago+ 0 comments

            Thank you!! wonderful code...Helped me when i was stuck tring to figure out the depth!

            0|
            ParentPermalink
          • ypahalajani 3 years ago+ 0 comments

            You used 2 arrays for storing left and right children. Genius! BTW: how do you come with such great logic and how much time does it take, GENERALLY ?

            0|
            ParentPermalink
          • prasanthsri09 3 years ago+ 0 comments

            Upvote! Upvote! Upvote!

            -2|
            ParentPermalink
          • spartacus_arena 3 years ago+ 0 comments

            @ludopulles thanks for your solution.

            0|
            ParentPermalink
          • ravin_dra 2 years ago+ 0 comments

            this is so cool

            0|
            ParentPermalink
          • long0133 2 years ago+ 1 comment

            Your solution may fail if input numbers are not in increment order. For example,

            3

            3 -1

            2 -1

            -1 -1

            2

            1

            1

            (while it works when in order:

            3

            2 -1

            3 -1

            -1 -1

            2

            1

            1 )

            One more example:

            5

            4 5

            2 -1

            -1 3

            -1 -1

            -1 -1

            1

            1

            The problem is because you use the input value as array index.

            0|
            ParentPermalink
            • paucarchris 2 years ago+ 0 comments

              Check your examples again, they're not BST. The first example says node 3 is a child of node 1, yet node 2 is a child of node 2?

              Second example works because it's a BST. Third example says node 4 and 5 are children of node 1, node 2 is its own child, node 3 is its own child.

              0|
              ParentPermalink
          • eloyekunle 1 year ago+ 0 comments

            That solution is one of the best for this problem.

            0|
            ParentPermalink
          • smithosagie24 1 year ago+ 0 comments

            Please, can you explain the depth method?

            0|
            ParentPermalink
          • cindysg 7 months ago+ 0 comments

            fantastic solution! thanks for sharing!

            0|
            ParentPermalink
          • Lherbeur 5 months ago+ 0 comments

            Very good idea!

            0|
            ParentPermalink
        • chued 4 years ago+ 0 comments

          While it is over engineering, your approach seems to be the learning intent of the problem. All 4 steps are outputs from prior problems. It should be a re-create with minor modifications exercise, hence the 'easy'. The wording of the problem, on the other hand...

          0|
          ParentPermalink
        • coder08122014 3 years ago+ 0 comments

          exactly i also did the same but i guess theres more optimal solution present

          0|
          ParentPermalink
      • SachitMNayak 4 years ago+ 0 comments

        yup! same here !

        0|
        ParentPermalink
      • nikolaijivkov 4 years ago+ 0 comments

        It certainly took a lot of writing, but I think it's easy becouse all of these tasks we had to solve in order to get to this one.

        I've certainly learned a lot from this site :)

        0|
        ParentPermalink
      • TheLastOrca 6 months ago+ 0 comments

        Yes, I did not have to construct a tree. I swapped them according to the levels. But struggled with traversing it after swapping.

        0|
        ParentPermalink
    • waitingkuo 4 years ago+ 0 comments

      same here. the algorithm is easy, but its implementation is so hard

      0|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature